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

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 }_{\mathrm{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.

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

References in corpus (14)

• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• The Scaling Window of the 2-SAT Transition
• Coloring random graphs
• A Measure of data-collapse for scaling
• Extremal Optimization for Graph Partitioning
• Simplest random K-satisfiability problem
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
• Phase coexistence and finite-size scaling in random combinatorial problems
• Extremal Optimization of Graph Partitioning at the Percolation Threshold
• Relaxation in graph coloring and satisfiability problems
• Jamming Model for the Extremal Optimization Heuristic

Cited by in corpus (15)

• Continuous extremal optimization for Lennard-Jones Clusters
• Stiffness Exponents for Lattice Spin Glasses in Dimensions d=3,...,6
• Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
• Comparing extremal and thermal Explorations of Energy Landscapes
• Numerical Results for Ground States of Spin Glasses on Bethe Lattices
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm
• Optimizing at the Ergodic Edge
• Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
• The Peculiar Phase Structure of Random Graph Bisection
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Sampling the ground-state magnetization of d-dimensional p-body Ising models
• The network source location problem: ground state energy, entropy and effects of freezing
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
• Algorithmic thresholds in combinatorial optimization depend on the time scaling