A spectral heuristic for bisecting random graphs
Amin Coja‐Oghlan · Symposium on Discrete Algorithms · 2005
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. The problem is NP-hard in the worst case. In this paper we analyze a spectral heuristic for the minimum bisection problem on random graphs Gn(p,p'), which are made up 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 n(p'-p) ≥ c0√np'In(np') for a certain constant c0 > 0, then with probability 1 - 0(1) as n ← ∞ the heuristic finds a minimum bisection of Gn(p,p') along with a certificate of optimality in polynomial time. Furthermore, we observe that the structure of the set of all minimum bisections of Gn(p,p') undergoes a phase transition as n(p' - p) = Θ(√np' In n). The heuristic solves instances in the subcritical, the critical, and the supercritical phase of the phase transition optimally with probability 1-o(1). These results extend the work of Boppana [5].