A Quasipolynomial (2 + ε)-Approximation for Planar Sparsest Cut

The (non-uniform) sparsest cut problem is the following classical
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. The sparsest cut problem has been a
driver for new algorithmic approaches. 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+\eps)$-approximation algorithm that runs in quasipolynomial
time. Our approach defines a new structural decomposition of an
optimal solution using a ``radial cuts'' 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 $\ell_1$-embeddings,
and achieves an $O(\sqrt{\log n})$-approximation in polynomial time.

• Algorithms and Theory