Volume 13 (2017) Article 8 pp. 1-22
APPROX-RANDOM 2015 Special Issue

The Minimum Bisection in the Planted Bisection Model

by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch

Received: December 19, 2015
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$.

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

DOI: 10.4086/toc.2017.v013a008

© 2017 Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
Licensed under a Creative Commons Attribution License (CC-BY)