On partitioning graphs via single commodity flows

In this paper we obtain improved upper and lower bounds for the best approximation factor for Sparsest Cut achievable in the cut-matching game framework proposed in Khandekar et al. [9]. We show that this simple framework can be used to design combinatorial algorithms that achieve O(log n) approximation factor and whose running time is dominated by a poly-logarithmic number of single-commodity max-flow computations. This matches the performance of the algorithm of Arora and Kale [2]. Moreover, we also show that it is impossible to get an approximation factor of better than Ω(√log n) in the cut-matching game framework. These results suggest that the simple and concrete abstraction of the cut-matching game may be powerful enough to capture the essential features of the complexity of Sparsest Cut.

Authors

• Lorenzo Orecchia
• Leonard J. Schulman
• Umesh V. Vazirani
• Nisheeth K. Vishnoi

Keywords

• edge-separator
• graph partitioning
• matrix exponential
• single-commodity max-flow
• sparsest cut
• spectral method