The minimum bisection in the planted bisection model

Abstract

In the planted bisection model a random graph $G(n,p_{+},p_{-})$ with $n$ vertices is created by partitioning the vertices randomly into two classes of equal size (up to $\pm 1$). Any two vertices that belong to the same class are linked by an edge with probability $p_{+}$ and any two that belong to different classes with probability $p_{-}<p_{+}$ independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If $p_{\pm }=2d_{\pm }/n$ for numbers $0\le d_{-}<d_{+}$ that remain fixed as $n\to \infty$, then w.h.p. the ``planted'' bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that $d_{+}-d_{-}>c\sqrt{d_{+}\ln d_{+}}$ for a certain constant $c>0$.

References in corpus (1)

• Extremal Cuts of Sparse Random Graphs

Cited by in corpus (1)

• Optimization on Sparse Random Hypergraphs and Spin Glasses