Graph Partitioning using Single Commodity Flows

摘要

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log~2 n) factor in O(m + n~(3/2)) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time O(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.