Approximating sparsest cut in graphs of bounded treewidth

DOI10.1007/978-3-642-15369-3_10zbMATH Open1304.68213arXiv1006.3970OpenAlexW2071588464MaRDI QIDQ3588403FDOQ3588403

Authors: Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra 

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Abstract: We give the first constant-factor approximation algorithm for Sparsest Cut with general demands in bounded treewidth graphs. In contrast to previous algorithms, which rely on the flow-cut gap and/or metric embeddings, our approach exploits the Sherali-Adams hierarchy of linear programming relaxations.

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

Recommendations

• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• Approximation algorithms for treewidth
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Integrality gaps for sparsest cut and minimum linear arrangement problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cited In (17)

• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Trimming weighted graphs of bounded treewidth
• The complexity status of problems related to sparsest cuts
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
• On algorithms employing treewidth for \(L\)-bounded cut problems
• The complexity of finding uniform sparsest cuts in various graph classes
• A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
• Pathwidth, trees, and random embeddings
• Integrating and sampling cuts in bounded treewidth graphs
• Cheeger-type approximation for sparsest \(st\)-cut
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Graph-Theoretic Concepts in Computer Science
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
• Integrality gaps for colorful matchings
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time

This page was built for publication: Approximating sparsest cut in graphs of bounded treewidth

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