Improved Approximation Algorithms for Minimum-weight Vertex Separators
Uriel Feige, Weizmann Institute and Microsoft Research
November 19, 2004

Abstract

A vertex separator in an n-vertex graph is a set of vertices whose removal breaks the graph into connected components, none of which is too large (say, larger than 2n/3). Finding small vertex separators is a basic primitive in many divide and conquer graph algorithms, among other things. We shall present an algorithm based on a "vector relaxation" of the problem that in any graph approximates the size of the minimum separator within a ratio of O(sqrt (log n)), improving over the previously best approximation ratio of O(log n). If time permits, we shall present various extensions of this result, such as an O(sqrt (log opt)) approximation ratio, a constant factor approximation ratio for graph families with an excluded minor, an O(sqrt (log opt)) approximation ratio for treewidth, and examples showing that the integrality ratio of our vector relaxation is no better than O(sqrt (log n)).

Joint work with MohammadTaghi Hajiaghayi and James Lee.