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

Stefan Boettcher and Allon G. Percus
Phys. Rev. E 69, 066703 – Published 24 June 2004

Abstract

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(n3.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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 10 February 2004

DOI:https://doi.org/10.1103/PhysRevE.69.066703

©2004 American Physical Society

Authors & Affiliations

Stefan Boettcher*

  • Department of Physics, Emory University, Atlanta, Georgia 30322, USA

Allon G. Percus

  • Computer & Computational Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA and UCLA Institute for Pure and Applied Mathematics, Los Angeles, California 90049, USA

  • *Electronic address: sboettc@emory.edu
  • Electronic address: percus@ipam.ucla.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 69, Iss. 6 — June 2004

Reuse & Permissions
Access Options

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×