 Volume 13 (2017) Article 8 pp. 1-22
APPROX-RANDOM 2015 Special Issue
The Minimum Bisection in the Planted Bisection Model
Revised: August 31, 2016
Published: September 23, 2017
$\newcommand\G{\vec G} \newcommand{\pplus}{p_{+}} \newcommand{\pminus}{p_{-}} \newcommand{\dplus}{d_{+}} \newcommand{\dminus}{d_{-}} \newcommand{\ppm}{p_{\pm }} \newcommand{\dpm}{d_{\pm }}$
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$.