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

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

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

(17)

• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• 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
• Pathwidth, trees, and random embeddings
• A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
• Integrating and sampling cuts in bounded treewidth graphs
• Cheeger-type approximation for sparsest \(st\)-cut
• An O( 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
• Integrality gaps for colorful matchings
• Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.

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)