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

Vladimir Kolmogorov, Jack Spalding-Jamieson

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, a…