Sparsest Cut by Random Contraction

From himtp
Jump to: navigation, search

(suggested by Jens Vygen)

Problem Statement

Let G be an undirected graph with edge weights c:E(G)\to\mathbb{R}_{\ge 0} and vertex weights w:V(G)\to\mathbb{R}_{\ge 0}. The sparsest cut problem asks for a nonempty proper subset U of the vertices that minimizes \frac{c(\delta(U))}{w(U)w(V(G)\setminus U)} (its sparsity). Often the interesting special case where w(v)=1 for all v\in V(G) is considered.

Consider the following random contraction algorithm, inspired by Karger's algorithm for the minimum cut problem (i.e., no denominators). In one iteration the algorithm randomly selects an edge e=\{u,v\} with probability proportional to \frac{c(e)}{w(u)w(v)} and contracts it, setting the weight of the new vertex to w(u)+w(v). The algorithm proceeds until only two vertices are left and outputs the corresponding cut.

What is known?

The best known approximation algorithm for the sparsest cut problem (Arora-Rao-Vazirani; ARV) has approximation ratio O(\sqrt{\log n}), where n=|V(G)|. For the minimum cut problem, Karger's random contraction algorithm outputs a minimum weight cut with probability at least \frac{2}{(n-1)n}. The corresponding property cannot hold for the sparsest cut problem; here the probability of finding a sparsest cut can be exponentially small. However, the algorithm works well in practice. It is much simpler than ARV and even Leighton-Rao, easy to implement, and fast, but its theoretical behaviour is not understood.


Is it true that with polynomially large probability the algorithm outputs a cut with sparsity at most O(\log n) times the optimum? Maybe even the expected value of the computed solution is O(\log n) times the optimum?

We know no counterexamples. The bound on the expectation is true for cliques with one appended edge, and for double-stars (trees with two vertices of degree \frac{n}{2}), for unit vertex weights. It is also true for circuits, but even paths are difficult to analyze. (Some of these easy results have been obtained in joint discussions with Nicolai Hähnle and Lukas Dreyer.)

Please add comments here