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

DOI10.1007/S10107-023-02044-1MaRDI QIDQ6589758FDOQ6589758

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)

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

zbMATH Keywords

linear programmingapproximation algorithmssparsest cut

Mathematics Subject Classification ID

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

Cites Work

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

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)