Graph partitioning using single commodity flows

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

Authors

• Rohit Khandekar
• Satish Rao
• Umesh V. Vazirani

Keywords

• edge-separator
• single commodity max-flow
• sparse cut
• spectral method