Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2008-08-11
J. Math. Phys. 49, 125219 (2008)
Physics
Condensed Matter
Statistical Mechanics
substantially revised section 2, changed figures 3, 4 and 6, made minor stylistic changes and added references
Scientific paper
10.1063/1.3043666
The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing exactly 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 near-optimal cutsizes (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition.
Boettcher Stefan
Goncalves Bruno
Istrate Gabriel
Percus Allon G.
Sumi Robert Z.
No associations
LandOfFree
The Peculiar Phase Structure of Random Graph Bisection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Peculiar Phase Structure of Random Graph Bisection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Peculiar Phase Structure of Random Graph Bisection will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-493385