Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
share
The fundamental sparsest cut problem takes as input a graph G together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands across the cuts. For n-node graphs G of treewidth k, , Krauthgamer, and Raghavendra (APPROX 2010) presented an algorithm that yields a factor-2^2^k approximation in time 2^O(k)·poly(n). Later, Gupta, Talwar and Witmer (STOC 2013) showed how to obtain a 2-approximation algorithm with a blown-up run time of n^O(k). An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time 2^O(k)·poly(n). In this paper, we make significant progress towards this goal, via the following results: (i) A factor-O(k^2) approximation that runs in time 2^O(k)·poly(n), directly improving the work of Chlamtáč et al. while keeping the run time single-exponential in k. (ii) For any ε>0, a factor-O(1/ε^2) approximation whose run time is 2^O(k^1+ε/ε)·poly(n), implying a constant-factor approximation whose run time is nearly single-exponential in k and a factor-O(log^2 k) approximation in time k^O(k)·poly(n). Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest.
READ FULL TEXT