Sparsest Cut on Bounded Treewidth Graphs
October 17, 2012
We consider the non-uniform sparsest cut problem. Given an underlying capacitated graph G and demands between the vertices of G (forming a demand graph H), the goal is to find a bipartition of the vertices that minimizes the ratio of the capacity of edges separated to the total demand separated by this partition. This is a generalization of the uniform sparsest cut problem, obtained by placing unit demand between every pair of vertices. These problems have been well-studied over the past 25 years for the purpose of developing approximation algorithms.
In this talk, we give a 2-approximation algorithm for the non-uniform sparsest cut problem with running time n^{O(k)}, where k is the treewidth of the underlying graph G. We complement this result by showing a hardness-of-approximation (even for treewidth-2 graphs) of 1/c, where c is the hardness of the max-cut problem on general graphs. This implies a hardness of 17/16 assuming P!=NP and 1/0.878 assuming the Unique Games Conjecture for treewidth-2 graphs G.
Our algorithm rounds a Sherali-Adams LP relaxation. We also show that the integrality gap of this LP remains at least 2-epsilon, even after polynomially many rounds of Sherali-Adams and even for treewidth-2 graphs G.
This is joint work with Anupam Gupta and Kunal Talwar (Microsoft Research SVC).
In this talk, we give a 2-approximation algorithm for the non-uniform sparsest cut problem with running time n^{O(k)}, where k is the treewidth of the underlying graph G. We complement this result by showing a hardness-of-approximation (even for treewidth-2 graphs) of 1/c, where c is the hardness of the max-cut problem on general graphs. This implies a hardness of 17/16 assuming P!=NP and 1/0.878 assuming the Unique Games Conjecture for treewidth-2 graphs G.
Our algorithm rounds a Sherali-Adams LP relaxation. We also show that the integrality gap of this LP remains at least 2-epsilon, even after polynomially many rounds of Sherali-Adams and even for treewidth-2 graphs G.
This is joint work with Anupam Gupta and Kunal Talwar (Microsoft Research SVC).