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 relax- ation 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 ex- pansion 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.
Citation
Full-length and extended version of proceedings paper to appear in ISCO 2024, arXiv:2403.04657 [math.OC]