Extremal Optimization at the Phase Transition of the 3-Coloring Problem

Details Extremal Optimization at the Phase Transition of the 3-Coloring Problem Extremal Optimization at the Phase Transition of the 3-Coloring Problem

2004-02-10

arxiv.org/abs/cond-mat/0402282v1

Physical Review E 69, 066703 (2004).

Physics

Condensed Matter

Disordered Systems and Neural Networks

RevTex4, 8 pages, 4 postscript figures, related information available at http://www.physics.emory.edu/faculty/boettcher/

Scientific paper

10.1103/PhysRevE.69.066703

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.

Affiliated with

Also associated with

No associations

Rating

Extremal Optimization at the Phase Transition of the 3-Coloring Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extremal Optimization at the Phase Transition of the 3-Coloring Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal Optimization at the Phase Transition of the 3-Coloring Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-167648