On partitioning graphs via single commodity flows

Abstract

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. Copyright 2008 ACM.