Approximating Sparsest Cut in Graphs of Bounded Treewidth
classification
💻 cs.DS
keywords
boundedgraphssparsesttreewidthalgorithmalgorithmsapproachapproximating
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.