Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands, and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n -vertex graphs G of treewidth k , Chlamtáč, Krauthgamer, and Raghavendra (APPROX 2010) presented an …