Graph Bisection AlgoriLhrns With Good A-veragc Case Behavior
Thang Bui, S.K. Chaudhuri, Mike Sipser · 1984
In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d 2 3, all suffciently large n and all b = o(nl-l/lTj), the algorithm finds the minimum bisection for almost all dregular lalxlled simple graphs with 2n nodes and bisection width b. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection width o(n'['). The algorii,hm differs from other graph bisection heuristics (as well :is from many heuristics for other NPcomp!cte problems 1 in several respects. Most notably: (1) the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimuin bisection,