Sparsest cut on bounded treewidth graphs
Anupam Gupta, Kunal Talwar, David K Witmer · 2013
We give a 2-approximation algorithm for the non-uniform Sparsest Cut problem that runs in time nO(k), where k is the treewidth of the graph. This improves on the previous 22k-approximation in time poly(n) 2O(k) due to Chlamtac et al. [18].