Finding almost-perfect graph bisections
April 20, 2011
ABSTRACT: We give a polynomial time algorithm that given a graph which admits a bisection cutting a fraction (1-eps) of edges, finds a bisection cutting a (1-g(eps)) fraction of edges where g(eps) goes to 0 as we make eps arbitrarily close to 0. One can take g(eps) = O(eps^{1/3} \log(1/eps)). Previously known algorithms for MaxBisection could only guarantee finding a bisection that cuts a fraction of edges bounded away from 1 (in fact less than 3/4) in such graphs. The known Unique-Games hardness results for MaxCut imply that one cannot achieve g(eps) < C eps^{1/2} for some absolute constant C.
Likewise, for the MinBisection problem, if the graph has a bisection cutting at most eps-fraction of the edges, our methods enable finding a bisection cutting at most O(eps^{1/3} \log(1/eps))-fraction of the edges.
The algorithms can also find cuts that are nearly-balanced (say with imbalance of at most 0.01) with value at least 1-O(eps^{1/2}) (for MaxBisection) and at most O(eps^{1/2}) (for MinBisection). These guarantees are optimal up to constant factors in the O(eps^{1/2}) term under the Unique Games and related conjectures.
Our general approach is simple to describe:
First, we show how to solve the problems if the graph is an expander or if the graph consists of many disjoint components, each of small measure.
Then, we show that every graph can be decomposed into disjoint components that are either expanders or have small measure, and how the cuts on different pieces may be merged appropriately.

Joint work with Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra and David Steurer.