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

作     者：Stefan Boettcher Allon G. Percus 

作者机构：[]Department of Physics Emory University Atlanta Georgia 30322 USA 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2004年第69卷第6期

页      面：066703-066703页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

基　　金：National Science Foundation, NSF, (DMR-0312510) Los Alamos National Laboratory, LANL 

主　　题：COMPUTATIONAL-COMPLEXITY SATISFIABILITY PROBLEMS GRAPH SEARCH MODEL Ground state extremum values complexity classes Phase transtormations system parameter DEGENERATE GROUND STATE Searches 

摘      要：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.