Sparsest cut on bounded treewidth graphs: Algorithms and hardness results

Anupam Gupta, Kunal Talwar, David Witmer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time nO(k), where k is the treewidth of the graph. This improves on the previous 22 k-approximation in time poly(n) 2O(k) due to Chlamtá̌c et al. [18]. To complement this algorithm, we show the following hardness results: If the Non-Uniform Sparsest Cut problem 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.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Number of pages10
StatePublished - 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
Country/TerritoryUnited States
CityPalo Alto, CA


  • APX-hardness
  • Graph separators
  • Sherali-adams
  • Sparsest cut
  • Treewidth
  • Unique games

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Sparsest cut on bounded treewidth graphs: Algorithms and hardness results'. Together they form a unique fingerprint.

Cite this