Improved approximation algorithms for minimum weight vertex separators

We develop the algorithmic theory of vertex separators and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L-1 (and even Euclidean embeddings) are insufficient but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an O(root log n) approximation for minimum ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Theta(root log n). We also prove an optimal O(log kappa)approximate max-flow/min-vertex-cut theorem for arbitrary vertex-capacitated multicommodity flow instances on k terminals. For uniform instances on any excluded-minor family of graphs, we improve this to O(1), and this yields a constant-factor approximation for minimum ratio vertex cuts in such graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best known ratio was O(log n). These results have a number of applications. We exhibit an O(root log n) pseudoapproximation for .nding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of O(root log opt), where opt is the size of an optimal separator, improving over the previous best bound of O(log opt). Likewise, we obtain improved approximation ratios for treewidth: in any graph of treewidth k, we show how to find a tree decomposition of width at most O(kappa root log kappa), whereas previous algorithms yielded O(kappa log kappa). For graphs excluding a fixed graph as a minor (which includes, e. g., bounded genus graphs), we give a constant-factor approximation for the treewidth. This in turn can be used to obtain polynomial-time approximation schemes for several problems in such graphs.