Approximating sparsest cut in graphs of bounded treewidth

DOI10.1007/978-3-642-15369-3_10MaRDI QIDQ3588403zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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( n)-approximation algorithm for directed sparsest cut
• Integrality gaps for sparsest cut and minimum linear arrangement problems

Cited in

(18)

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

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)