Approximating Sparsest Cut in Graphs of Bounded Treewidth
Eden Chlamtáč, Robert Krauthgamer, Prasad Raghavendra · arXiv (Cornell University) · 2010
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.