pdf icon
Volume 13 (2017) Article 8 pp. 1-22
APPROX-RANDOM 2015 Special Issue
The Minimum Bisection in the Planted Bisection Model
Received: December 19, 2015
Revised: August 31, 2016
Published: September 23, 2017
Download article from ToC site:
[PDF (286K)]    [PS (1486K)]    [PS.GZ (337K)]
[Source ZIP]
Keywords: random graphs, minimum bisection, planted bisection, belief propagation
ACM Classification: G.2.2
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

$ \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).