Graph Partitioning using Single Commodity Flows
Rohit Khandekar, Post-doctoral associate, University of Waterloo
Friday February 3rd, 2006

Abstract

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 well using single
commodity max-flow computations which are fast both 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).