Finding almost-perfect graph bisections

with Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, Yuan Zhou. ICS 2011.

abstract

We give a polynomial time algorithm that given a graph which admits a bisection cutting a fraction $(1-\varepsilon)$ of edges, finds a bisection cutting a $(1-g(\varepsilon))$ fraction of edges where $g(\varepsilon) \to 0$ as $\varepsilon\to 0$ . One can take $g(\varepsilon) = O(\sqrt[3]{\varepsilon}\log(1/\varepsilon))$ . Previously known algorithms for Max Bisection 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
imply that one cannot achieve $g(\varepsilon) \le C \sqrt{\varepsilon}$ for some absolute constant $C$ .

Likewise, for the MIN BISECTION problem, if the graph has a bisection cutting at most $\varepsilon$ -fraction of the edges, our methods enable finding a bisection cutting at most $O(\sqrt[3]{\varepsilon}\log(1/\varepsilon))$ -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(\sqrt{\varepsilon})$ (for MAX BISECTION) and at most $O(\sqrt{\varepsilon})$ (for MIN BISECTION). These guarantees are optimal up to constant factors in the $O(\sqrt{\varepsilon})$ 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.