A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
This addresses a fundamental graph partitioning problem with applications in areas like VLSI design and network analysis, though it is incremental as it builds on existing SDP and MMWU frameworks.
The paper tackles the minimum balanced vertex separator problem in graphs by presenting a family of fast pseudo-approximation algorithms that produce a separator of size O(OPT_c * sqrt(log n / ε)) in O(n^{O(ε)} m^{1+o(1)}) time, achieving the best-known approximation ratio for small constant ε.
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 $c\in(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 $Î(1)$-balanced vertex separator of size $O({\rm OPT}_c\cdot\sqrt{(\log n)/\varepsilon})$ for any value $\varepsilon\in[Î(1/\log(n)),Î(1)]$. In particular, for any function $f(n)=Ï(1)$ (including $f(n)=\log\log n$, for instance), we can produce a vertex separator of size $O({\rm OPT}_c\cdot\sqrt{\log n}\cdot f(n))$ in time $O(m^{1+o(1)})$. Moreover, for an arbitrarily small constant $\varepsilon=Î(1)$, our algorithm also achieves the best-known approximation ratio for this problem in $O(m^{1+Î(\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.