Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

Allon Percus, Gabriel Istrate, Bruno Tavares Gonçalves, Robert Z. Sumi, Stefan Boettcher . The Peculiar Phase Structure of Random Graph Bisection. Journal of Mathematical Physics, 49 (12), p. 125219, 2008.

Abstract: The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing n/2 vertices, while minimizing the number of "cut" edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays certain familiar properties, but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can find cutsizes that are asymptotically within a factor 1 of optimal -- and possibly even the optimum itself -- in polynomial time for typical instances near the phase transition.

A freely available preprint is located at

Keywords: random graph bisection


Posted by Gabriel Istrate


© Ad Astra 2001-2013