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

We investigate the phase transition in vertex coloring on random graphs, using the extremal optimization heuristic. Three-coloring is among the hardest combinatorial optimization problems and is equivalent to a 3-state anti-ferromagnetic Potts model. Like many other such optimization problems, it has been shown to exhibit a phase transition in its ground state behavior under variation of a system parameter: the graph’s mean vertex degree. This phase transition is often associated with the instances of highest complexity. We use extremal optimization to measure the ground state cost and the “backbone,” an order parameter related to ground state overlap, averaged over a large number of instances near the transition for random graphs of size n up to 512. For these graphs, benchmarks show that extremal optimization reaches ground states and explores a sufficient number of them to give the correct backbone value after about O(n^3.5) update steps. Finite size scaling yields a critical mean degree value α_c=4.703(28). Furthermore, the exploration of the degenerate ground states indicates that the backbone order parameter, measuring the constrainedness of the problem, exhibits a first-order phase transition.