Revised: August 31, 2016

Published: September 23, 2017

**Keywords:**random graphs, minimum bisection, planted bisection, belief propagation

**Categories:**graphs, algorithms, random graphs, bisection, minimum bisection, planted, planted bisection, belief propagation, RANDOM, APPROX-RANDOM 2015 special issue

**ACM Classification:**G.2.2

**AMS Classification:**68Q17, 52C07, 11H06, 11H31, 05B40

**Abstract:**
[Plain Text Version]

In the planted bisection model a random graph $\G(n,\pplus,\pminus )$ with $n$ vertices is created by partitioning the vertices randomly into two classes of equal size (up to $\pm1$). Any two vertices that belong to the same class are linked by an edge with probability $\pplus$ and any two that belong to different classes with probability $\pminus < \pplus$ independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If $\ppm =2\dpm /n$ for numbers $0\leq \dminus < \dplus $ 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 $\dplus -\dminus > c\sqrt{\dplus \ln \dplus }$ for a certain constant $c> 0$.

A preliminary version of this paper appeared in the Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM 2015).