The Peculiar Phase Structure of Random Graph Bisection

Abstract

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.

substantially revised section 2, changed figures 3, 4 and 6, made minor stylistic changes and added references

References in corpus (7)

• Attack vulnerability of complex networks
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Nature's Way of Optimizing
• A variational description of the ground state structure in random satisfiability problems
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Monotone properties of random geometric graphs have sharp thresholds
• Extremal Optimization of Graph Partitioning at the Percolation Threshold

Cited by in corpus (8)

• Extremal Cuts of Sparse Random Graphs
• Collective dynamics in sparse networks
• Conjecture on the maximum cut and bisection width in random regular graphs
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Belief propagation for graph partitioning
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Bipartitioning of directed and mixed random graphs
• Cluster structure of optimal solutions in bipartitioning of small worlds