TITLE: Improved approximation algorithms for minimum-weight vertex
separators

SPEAKER: Uri Feige,  
         The Weizmann Institute and Microsoft Research

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.