## Simulated Annealing for Graph Bisection

**Mark Jerrum and Gregory Sorkin**
*Abstract:* We resolve in the affirmative a question of
Boppana and Bui: whether simulated annealing can, with high
probability and in polynomial time, find the optimal bisection of a
random graph in *G_npr* when *p - r = Theta(n^(Delta -
2))* for *Delta <= 2*. (The random graph model
*G_npr* specifies a ``planted'' bisection of density *r*,
separating two *n/2*-vertex subsets of slightly higher density
*p*.) We show that simulated ``annealing'' at an appropriate
fixed temperature (i.e., the Metropolis algorithm) finds the unique
smallest bisection in *O(n^(2+epsilon))* steps with very high
probability, provided *Delta > 11/6*. (By using a slightly
modified neighborhood structure, the number of steps can be reduced
to *O(n^(1+epsilon))*.) We leave open the question of whether
annealing is effective for *Delta* in the range *3/2 <
Delta <= 11/6*, whose lower limit represents the threshold at
which the planted bisection becomes lost amongst other random small
bisections. It remains open whether hillclimbing (i.e., annealing
at temperature 0) solves the same problem.

*LFCS report ECS-LFCS-93-260,
April 1993.*

Previous |

Index |

Next