Graph Partitioning using Single Commodity Flows

Rohit Khandekar, University of Waterloo

Graph partitioning is one of the fundamental optimization problems 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 talk is a sequel of my previous talk and is a joint work with Satish Rao and Umesh Vazirani (UC Berkeley).