Fast Approximation Algorithms for Balanced Edge and Vertex Separators

Abstract

We present a family of fast pseudo-approximation algorithms for the minimum balanced element cut problem in a graph, which includes vertex and edge separators. Given a graph $G=(V,E)$ with polynomially-bounded finite integer element weights with $n$ vertices and $m$ edges, and a (constant) balance parameter $c\in (0,1/2)$, where $G$ has some (unknown) $c$-balanced element cut of size $OP{T}_c$, we give a (Monte-Carlo randomized) algorithm running in $O(n^{\epsilon }{m}^{1+o(1)})$ time that produces a $\Theta (1)$-balanced element cut of size $O(OP{T}_c\cdot \sqrt{(\log n)/\epsilon })$ for any value $\epsilon \in [\Theta (1/\log (n)),\Theta (1)]$. Our algorithms are based on a semidefinite programming (SDP) relaxation of the problem. A standard approach to solving an SDP relaxation for this kind of problem would use the primal-dual Matrix Multiplicative Weights Update framework of Arora and Kale, but this framework does not seem to apply, since we cannot express all of our SDPs primal variables explicitly. Instead, we present a new MMWU framework for our problem that allows us to represent some of our variables implicitly. We also extend our framework to a general "Partial-variable MMWU framework", which we expect will be useful for future work. Our oracle for the balanced element cut problem within our framework uses $O(n^{\epsilon }\text{polylog}(n))$ almost-linear time maximum-flow computations, and would be sped up if the time complexity of maximum-flow improves. For graphs with padding bound $\beta$, another oracle gives an $O(\sqrt{\beta }/\epsilon )$ approximation in $m^{1+o(1)}{n}^{\epsilon }\mathrm{polylog}(n)$ time. It is known that $\beta \le O(\log h)$ for $K_h$-minor-free graphs (and in particular $\beta \le O(\log n)$).

arXiv comment27 pages