Graph partitioning using single commodity flows
Rohit Khandekar, Satish B. Rao, Umesh V. Vazirani · Journal of the ACM · 2009
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.