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 f…