Constant Factor Approximation for Balanced Cut in the PIE model

Abstract

We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V partitioned into two clusters $L$ and $R$ of equal size. Let $G$ be an arbitrary graph on $V$ with no edges between $L$ and $R$. Let $E_{random}$ be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under permutation of vertices in $L$ and in $R$). Then we say that $G+E_{random}$ is a graph with permutation-invariant random edges. We present an approximation algorithm for the Balanced Cut problem that finds a balanced cut of cost $O(|E_{random}|)+n\text{polylog}(n)$ in this model. In the regime when $|E_{random}|=\Omega (n\text{polylog}(n))$, this is a constant factor approximation with respect to the cost of the planted cut.

Full version of the paper at the 46th ACM Symposium on the Theory of Computing (STOC 2014). 32 pages