  Computing the edge expansion of a graph is a famously hard combinatorial
problem for which there have been many approximation studies. We present two
variants of exact algorithms using semidefinite programming (SDP) to compute
this constant for any graph. The first variant uses the SDP relaxation first to
reduce the search space considerably. One implementation of this variant
applies then an SDP-based branch-and-bound algorithm, along with heuristic
search. The second implementation transforms the problem into an instance of a
max-cut problem and solves this using an SDP-based state-of-the-art solver. Our
second variant to compute the edge expansion uses Dinkelbach's algorithm for
fractional programming. This is, we have to solve a parametrized optimization
problem and again we use semidefinite programming to obtain solutions of the
parametrized problems. Numerical results demonstrate that with our algorithms
one can compute the edge expansion on graphs up to 400 vertices in a routine
way, including instances where standard branch-and-cut solvers fail. To the
best of our knowledge, these are the first SDP-based solvers for computing the
edge expansion of a graph.
