Approximating Sparsest Cut in Graphs of Bounded Treewidth

Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra

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.

Knowledge Graph



Sign up or login to leave a comment