Graph Partitioning using Single Commodity Flows

that has been extensively studied both in theory and practice. In this
talk, we shall consider the problem of approximating the sparsest cuts
in graphs. Almost all the previous algorithms for this problem, use
either eigenvector computations, multi-commodity flows, or solving
semi-definite programs as sub-routines. While eigenvector based
approaches yield poor approximation guarantees, the multi-commodity
flows or SDP based algorithms are slow.

We show that the sparsest cuts can be approximated within a factor of
O(log2 n) using single commodity max-flow computations which are fast
in theory and perhaps more so in practice. Our algorithm iteratively
computes max-flows to embed a complete graph and yields a certificate of expansion. Our technique can also be extended to obtain fast approximations for the balanced separator problem.

This is a joint work with Satish Rao and Umesh Vazirani (UC Berkeley).