Relaxation in graph coloring and satisfiability problems
arXiv:cond-mat/9810144 · doi:10.1103/PhysRevE.59.3983
Abstract
Using T=0 Monte Carlo simulation, we study the relaxation of graph coloring (K-COL) and satisfiability (K-SAT), two hard problems that have recently been shown to possess a phase transition in solvability as a parameter is varied. A change from exponentially fast to power law relaxation, and a transition to freezing behavior are found. These changes take place for smaller values of the parameter than the solvability transition. Results for the coloring problem for colorable and clustered graphs and for the fraction of persistent spins for satisfiability are also presented.
13 pages, 22 figures. Several changes to text, figures added, section on feromagnetic model moved to a separate publication. Accepted for publication in Phys Rev. E
References in corpus (12)
- Phase Transition in the Number Partitioning Problem
- Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
- Probabilistic Analysis of the Number Partitioning Problem
- Tricritical Points in Random Combinatorics: the (2+p)-SAT case
- Numerical study of a short-range p-spin glass model in three dimensions
- An Iterative Solution of the Three-colour Problem on a Random Lattice
- Statistical mechanics of the multi-constraint continuous knapsack problem
- Coloring Random Triangulations
- Potts Models on Feynman Diagrams
- Field theoretic approach to the counting problem of Hamiltonian cycles of graphs
- Statistical Mechanics of a Two-Dimensional System with Long Range Interaction
- Optimization by Move--Class Deflation
Cited by in corpus (9)
- Critical phenomena in complex networks
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Phase Transitions in the Coloring of Random Graphs
- Extremal Optimization at the Phase Transition of the 3-Coloring Problem
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Freezing in random graph ferromagnets
- Approximate analysis of search algorithms with "physical" methods
- Extremal optimization for sensor report pre-processing
- Two Combinatorial Models with identical Statics yet different Dynamics