2004/02/10 by Stefan Boettcher, Allon G. Percus · 4 citations
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #Optimization and Search Problems #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.69.066703
published as Physical Review E 69, 066703 (2004). · RevTex4, 8 pages, 4 postscript figures, related information available at http://www.physics.emory.edu/faculty/boettcher/
arxiv created 2004/02/10 · openalex publication_date 2004/06/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 alpha(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.