A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph

arXiv:2603.15782v1 Announce Type: new
Abstract: We present a family of fast pseudo-approximation algorithms for the minimum balanced vertex separator problem in a graph. Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, and a (constant) balance parameter $cin(0,1/2)$, where $G$ has some (unknown) $c$-balanced vertex separator of size ${rm OPT}_c$, we give a (Monte-Carlo randomized) algorithm running in $O(n^{O(varepsilon)}m^{1+o(1)})$ time that produces a $Theta(1)$-balanced vertex separator of size $O({rm OPT}_ccdotsqrt{(log n)/varepsilon})$ for any value $varepsilonin[Theta(1/log(n)),Theta(1)]$. In particular, for any function $f(n)=omega(1)$ (including $f(n)=loglog n$, for instance), we can produce a vertex separator of size $O({rm OPT}_ccdotsqrt{log n}cdot f(n))$ in time $O(m^{1+o(1)})$. Moreover, for an arbitrarily small constant $varepsilon=Theta(1)$, our algorithm also achieves the best-known approximation ratio for this problem in $O(m^{1+Theta(varepsilon)})$ time.
The algorithms are based on a semidefinite programming (SDP) relaxation of the problem, which we solve using the Matrix Multiplicative Weight Update (MMWU) framework of Arora and Kale. Our oracle for MMWU uses $O(n^{O(varepsilon)}text{polylog}(n))$ almost-linear time maximum-flow computations, and would be sped up if the time complexity of maximum-flow improves.