Extremal optimization at the phase transition of the three-coloring problem

Area of Science:

• Computational Complexity
• Statistical Physics
• Graph Theory

Background:

• Three-coloring random graphs is a computationally hard problem, equivalent to a 3-state anti-ferromagnetic Potts model.
• Many hard optimization problems exhibit phase transitions in their ground state behavior as system parameters change.
• These phase transitions often correlate with problem instances of maximum complexity.

Purpose of the Study:

• To investigate the phase transition in vertex coloring on random graphs.
• To measure ground state properties and the 'backbone' order parameter near the transition.
• To determine the critical mean degree and characterize the nature of the phase transition.

Main Methods:

• Employed the extremal optimization heuristic to study random graphs up to size n=512.
• Measured ground state cost and the backbone order parameter, averaged over numerous instances.
• Utilized finite size scaling analysis to determine critical parameters.

Main Results:

• Extremal optimization efficiently reached ground states and explored sufficient states for accurate backbone measurement (O(n^3.5) steps).
• A critical mean degree value of alpha(c) = 4.703(28) was identified.
• Exploration of degenerate ground states revealed that the backbone order parameter exhibits a first-order phase transition.

Conclusions:

• The study confirms a phase transition in random graph three-coloring.
• The backbone order parameter effectively measures problem constrainedness and signals a first-order transition.
• Extremal optimization is a viable heuristic for studying complex optimization problems and their phase transitions.