{
  "id": "cond-mat/0402282",
  "version": "v1",
  "published": "2004-02-10T14:46:56.000Z",
  "updated": "2004-02-10T14:46:56.000Z",
  "title": "Extremal Optimization at the Phase Transition of the 3-Coloring Problem",
  "authors": [
    "Stefan Boettcher",
    "Allon G. Percus"
  ],
  "comment": "RevTex4, 8 pages, 4 postscript figures, related information available at http://www.physics.emory.edu/faculty/boettcher/",
  "journal": "Physical Review E 69, 066703 (2004).",
  "doi": "10.1103/PhysRevE.69.066703",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech"
  ],
  "abstract": "We investigate the phase transition of the 3-coloring problem on random graphs, using the extremal optimization heuristic. 3-coloring is among the hardest combinatorial optimization problems and is closely related 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 graphs up to this size, 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 gives a critical mean degree value $\\alpha_{\\rm 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-02-10T14:46:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "phase transition",
      "extremal optimization reaches ground states",
      "graphs mean vertex degree",
      "random graphs",
      "order parameter"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Phys. Rev. E"
    },
    "note": {
      "typesetting": "RevTeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}