A spectral heuristic for bisecting random graphs

The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. Computing a minimum bisection is NP‐hard in the worst case. In this paper we study a spectral heuristic for bisecting random graphs G_n(p,p′) with a planted bisection obtained as follows: partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p′ and edges crossing the partition with probability p independently. If , where c₀ is a suitable constant, then with probability 1 ? o(1) the heuristic finds a minimum bisection of G_n(p,p′) along with a certificate of optimality. Furthermore, we show that the structure of the set of all minimum bisections of G_n(p,p′) undergoes a phase transition as . The spectral heuristic solves instances in the subcritical, the critical, and the supercritical phases of the phase transition optimally with probability 1 ? o(1). These results extend previous work of Boppana 5 . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006