Sparsest cut on bounded treewidth graphs: algorithms and hardness results

DOI10.1145/2488608.2488644MaRDI QIDQ5495798zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Kunal Talwar, David Witmer

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1347

zbMATH Keywords

APX-hardnessgraph separatorsSherali-Adamssparsest cuttreewidthunique games

Mathematics Subject Classification ID

Trees (05C05) Graph designs and isomorphic decomposition (05C51) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Linear programming (90C05)

Abstract: We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time $n^{O(k)}$, where $k$ is the treewidth of the graph. This improves on the previous $2^{2^k}$-approximation in time $poly(n)2^{O(k)}$ due to Chlamt'av{c} et al. To complement this algorithm, we show the following hardness results: If the Non-Uniform Sparsest Cut problem has a $ho$-approximation for series-parallel graphs (where $hogeq1$), then the Max Cut problem has an algorithm with approximation factor arbitrarily close to $1/ho$. Hence, even for such restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard to approximate better than $17/16-epsilon$ for $epsilon>0$; assuming the Unique Games Conjecture the hardness becomes $1/alph{a}_{GW}-epsilon$. For graphs with large (but constant) treewidth, we show a hardness result of $2-epsilon$ 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.

Recommendations

• Approximating sparsest cut in graphs of bounded treewidth
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• The complexity of finding uniform sparsest cuts in various graph classes
• The complexity status of problems related to sparsest cuts
• On the hardness of approximating Multicut and Sparsest-Cut

Cited in

(20)

• An O( n)-approximation algorithm for directed sparsest cut
• Approximating graph-constrained max-cut
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• Integrality gaps for colorful matchings
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• A comprehensive analysis of polyhedral lift-and-project methods
• The complexity status of problems related to sparsest cuts
• Max-cut under graph constraints
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Approximating sparsest cut in graphs of bounded treewidth
• The complexity of finding uniform sparsest cuts in various graph classes
• A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
• Survivable network design for group connectivity in low-treewidth graphs
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
• The telephone k-multicast problem
• Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
• Direct product multicommodity max-concurrent-flow min-sparse-cut theorem
• Linear programming hierarchies collapse under symmetry

This page was built for publication: Sparsest cut on bounded treewidth graphs: algorithms and hardness results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495798)