A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time

DOI10.1007/S10107-023-02044-1MaRDI QIDQ6589758zbMATH OpenFDO

Authors Vincent Cohen-Addad, Tobias Mömke, Víctor Verdugo

Publication date 20 August 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

linear programmingapproximation algorithmssparsest cut

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35)

Recommendations

• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• Approximating sparsest cut in graphs of bounded treewidth
• The complexity of finding uniform sparsest cuts in various graph classes

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 7788514 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A quasipolynomial (2 + ε )-approximation for planar sparsest cut
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• An improved parameterized algorithm for treewidth
• Coarse differentiation and multi-flows in planar graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Euclidean distortion and the sparsest cut
• Expander flows, geometric embeddings and graph partitioning
• Flow-cut gaps for integer and fractional multiflows
• LP formulations for polynomial optimization problems
• Multicommodity flows in planar graphs
• On the Lambert \(w\) function
• On the hardness of approximating Multicut and Sparsest-Cut
• Pathwidth, trees, and random embeddings
• Sparsest cuts and bottlenecks in graphs
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• Tree-width and the Sherali-Adams operator

This page was built for publication: A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time

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