A quasipolynomial (2 + ?)-approximation for planar sparsest cut

Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li

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


The (non-uniform) sparsest cut problem is the following graph-partitioning problem: given a "supply"graph, and demands on pairs of vertices, delete some subset of supply edges to minimize the ratio of the supply edges cut to the total demand of the pairs separated by this deletion. Despite much effort, there are only a handful of nontrivial classes of supply graphs for which constant-factor approximations are known. We consider the problem for planar graphs, and give a (2+)-approximation algorithm that runs in quasipolynomial time. Our approach defines a new structural decomposition of an optimal solution using a "patching"primitive. We combine this decomposition with a Sherali-Adams-style linear programming relaxation of the problem, which we then round. This should be compared with the polynomial-time approximation algorithm of Rao (1999), which uses the metric linear programming relaxation and ?1-embeddings, and achieves an O(?logn)-approximation in polynomial time.

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Number of pages14
ISBN (Electronic)9781450380539
StatePublished - Jun 15 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

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


Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
CityVirtual, Online


  • Approximation algorithms
  • Graph Partitioning
  • LP Rounding
  • Non-Uniform Sparsest Cut
  • Planar Graphs

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'A quasipolynomial (2 + ?)-approximation for planar sparsest cut'. Together they form a unique fingerprint.

Cite this