Revised: August 31, 2016
Published: September 23, 2017
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).