Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results

Abstract

We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time $n^{O(k)}$, where $k$ is the treewidth of the graph. This improves on the previous $2^{2^k}$-approximation in time $\poly(n) 2^{O(k)}$ due to Chlamtáč et al. To complement this algorithm, we show the following hardness results: If the Non-Uniform Sparsest Cut problem has a $\ddot{I}$-approximation for series-parallel graphs (where $\ddot{I}\ge 1$), then the Max Cut problem has an algorithm with approximation factor arbitrarily close to $1/\ddot{I}$. Hence, even for such restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard to approximate better than $17/16-\hat{I}\mu$ for $\hat{I}\mu >0$; assuming the Unique Games Conjecture the hardness becomes $1/\hat{I}{\pm }_{GW}-\hat{I}\mu$. For graphs with large (but constant) treewidth, we show a hardness result of $2-\hat{I}\mu$ assuming the Unique Games Conjecture. Our algorithm rounds a linear program based on (a subset of) the Sherali-Adams lift of the standard Sparsest Cut LP. We show that even for treewidth-2 graphs, the LP has an integrality gap close to 2 even after polynomially many rounds of Sherali-Adams. Hence our approach cannot be improved even on such restricted graphs without using a stronger relaxation.