Theory of Computing
-------------------
Title : The Minimum Bisection in the Planted Bisection Model
Authors : Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
Volume : 13
Number : 8
Pages : 1-22
URL : https://theoryofcomputing.org/articles/v013a008
Abstract
--------
In the planted bisection model a random graph $G(n,p_+,p_-)$
with $n$ vertices is created by partitioning the vertices randomly
into two classes of equal size (up to $+/- 1$). Any two vertices that
belong to the same class are linked by an edge with probability
$p_+$ and any two that belong to different classes with probability
$p_- < p_+$ independently. The planted bisection model has been
used extensively to benchmark graph partitioning algorithms. If
$p_{+/-}=2d_{+/-}/n$ for numbers $0\leq d_- < d_+$ 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 $d_+ -d_- > c\sqrt{d_+ \ln d_+}$ 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).