Graph partitioning using single commodity flows

Abstract

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log 2 n) factor in (m + n 3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time (m + n 2). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log 2 n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time. © 2009 ACM.