A quasipolynomial (2 + ε)-approximation for planar sparsest cut
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021•dl.acm.org
The (non-uniform) sparsest cut problem is the following graph-partitioning problem: given a
“supply” graph, and demands on pairs of vertices, delete some subset of supply edges to
minimize the ratio of the supply edges cut to the total demand of the pairs separated by this
deletion. Despite much effort, there are only a handful of nontrivial classes of supply graphs
for which constant-factor approximations are known. We consider the problem for planar
graphs, and give a (2+)-approximation algorithm that runs in quasipolynomial time. Our …
“supply” graph, and demands on pairs of vertices, delete some subset of supply edges to
minimize the ratio of the supply edges cut to the total demand of the pairs separated by this
deletion. Despite much effort, there are only a handful of nontrivial classes of supply graphs
for which constant-factor approximations are known. We consider the problem for planar
graphs, and give a (2+)-approximation algorithm that runs in quasipolynomial time. Our …
The (non-uniform) sparsest cut problem is the following graph-partitioning problem: given a “supply” graph, and demands on pairs of vertices, delete some subset of supply edges to minimize the ratio of the supply edges cut to the total demand of the pairs separated by this deletion. Despite much effort, there are only a handful of nontrivial classes of supply graphs for which constant-factor approximations are known.
We consider the problem for planar graphs, and give a (2+)-approximation algorithm that runs in quasipolynomial time. Our approach defines a new structural decomposition of an optimal solution using a “patching” primitive. We combine this decomposition with a Sherali-Adams-style linear programming relaxation of the problem, which we then round. This should be compared with the polynomial-time approximation algorithm of Rao (1999), which uses the metric linear programming relaxation and ℓ1-embeddings, and achieves an O(√logn)-approximation in polynomial time.
![](/scholar/images/qa_favicons/acm.org.png)