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