Sparsest cut on bounded treewidth graphs
Authors:
Open Access
- 1 June 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 281-290
Abstract
We give a 2-approximation algorithm for the non-uniform Sparsest Cut problem that runs in time nO(k), where k is the treewidth of the graph. This improves on the previous 22k-approximation in time poly(n) 2O(k) due to Chlamtac et al. [18]. To complement this algorithm, we show the following hardness results: If the non-uniform Sparsest Cut has a ρ-approximation for series-parallel graphs (where ρ ≥ 1), then the MaxCut problem has an algorithm with approximation factor arbitrarily close to 1/ρ. Hence, even for such restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard to approximate better than 17/16 - ε for ε 0; assuming the Unique Games Conjecture the hardness becomes 1/αGW - ε. For graphs with large (but constant) treewidth, we show a hardness result of 2 - ε assuming the Unique Games Conjecture. Our algorithm rounds a linear program based on (a subset of) the Sherali-Adams lift of the standard Sparsest Cut LP. We show that even for treewidth-2 graphs, the LP has an integrality gap close to 2 even after polynomially many rounds of Sherali-Adams. Hence our approach cannot be improved even on such restricted graphs without using a stronger relaxation.Keywords
This publication has 39 references indexed in Scilit:
- Noise stability of functions with low influences: Invariance and optimalityAnnals of Mathematics, 2010
- Coarse Differentiation and Multi-flows in Planar GraphsDiscrete & Computational Geometry, 2009
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- Polynomial flow-cut gaps and hardness of directed cut problemsJournal of the ACM, 2009
- Approximation Algorithms for TreewidthAlgorithmica, 2008
- Euclidean distortion and the sparsest cutJournal of the American Mathematical Society, 2007
- On the impossibility of dimension reduction in l 1Journal of the ACM, 2005
- Cuts, Trees and ℓ1-Embeddings of Graphs*Combinatorica, 2004
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986