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’10) presented an algorithm that yields a factor-2 ^2k approximation in time 2 ^O(k ⁾ · n ^O(1 ⁾. Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime 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 ⁾ · n ^O(1 ⁾. In this article, we make significant progress towards this goal via the following results: (i) A factor-O(k ²) approximation that runs in time 2 ^O(k ⁾ ·n ^O(1 ⁾, directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k. (ii) For any ε ∈ (0, 1], a factor-O(1/ε ²) approximation whose runtime is 2 ^O( ^{k 1}+ ^{ε /}ε ⁾ · n ^O(1 ⁾, implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor-O(log ² k) approximation in time k ^O(k ⁾ · n ^O(1 ⁾. Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest.