Coloring random graphs

Abstract

We study the graph coloring problem over random graphs of finite average connectivity $c$. Given a number $q$ of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on $q$, we find the precise value of the critical average connectivity $c_q$. Moreover, we show that below $c_q$ there exist a clustering phase $c\in [c_d,c_q]$ in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.

4 pages, 1 figure, version to app. in PRL

References in corpus (1)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm

Cited by in corpus (99)

• Critical phenomena in complex networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Phase Transitions in the Coloring of Random Graphs
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Clustering of solutions in the random satisfiability problem
• Survey propagation: an algorithm for satisfiability
• Jamming versus Glass Transitions
• A Landscape Analysis of Constraint Satisfaction Problems
• The number of matchings in random graphs
• Learning by message-passing in networks of discrete synapses
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• On the dynamics of the glass transition on Bethe lattices
• Replica bounds for diluted non-Poissonian spin systems
• Entropies of complex networks with hierarchically constrained topologies
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Landscape of solutions in constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the critical slowing down exponents of mode coupling theory
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Constraint satisfaction problems with isolated solutions are hard
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Pairs of SAT Assignment in Random Boolean Formulae
• Clustering of non-ergodic eigenstates in quantum spin glasses
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Networking - A Statistical Physics Perspective
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• From Large Scale Rearrangements to Mode Coupling Phenomenology
• Quantum algorithm for energy matching in hard optimization problems
• Potts Glass on Random Graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Geometrical organization of solutions to random linear Boolean equations
• Random multi-index matching problems
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Clustering analysis of the ground-state structure of the vertex-cover problem
• A frozen glass phase in the multi-index matching problem
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Near optimal configurations in mean field disordered systems
• Phase transitions in the $q$-coloring of random hypergraphs
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• Spin models on random graphs with controlled topologies beyond degree constraints
• Algorithmic Thresholds in Mean Field Spin Glasses
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• The cavity method for large deviations
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Exactly solvable models of adaptive networks
• On the phase transitions of graph coloring and independent sets
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Sudden emergence of q-regular subgraphs in random graphs
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
• A hard-sphere model on generalized Bethe lattices: Statics
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• A theory of non-equilibrium local search on random satisfaction problems
• Planting colourings silently
• Compressed sensing reconstruction using Expectation Propagation
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Properties of atypical graphs from negative complexities
• Solution-space structure of (some) optimization problems
• An exact study of phase transitions in mean field Potts models
• The dynamics of proving uncolourability of large random graphs I. Symmetric Colouring Heuristic
• Clustering in Hilbert space of a quantum optimization problem
• Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach
• Constraint optimization and landscapes
• Optimal Location of Sources in Transportation Networks
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• Palette-colouring: a belief-propagation approach
• Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
• Susceptibility Propagation for Constraint Satisfaction Problems
• A hard-sphere model on generalised Bethe lattices: Dynamics
• Using Differential Evolution for the Graph Coloring
• An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
• Replication-based Inference Algorithms for Hard Computational Problems
• Spin-glass behaviour on random lattices
• Statistical mechanics of optimization problems
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Phase transition in the bipartite z-matching
• Computing a Knot Invariant as a Constraint Satisfaction Problem
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Perturbed Message Passing for Constraint Satisfaction Problems
• Inside the clustering window for random linear equations
• The replica symmetric solution for Orthogonally Constrained Heisenberg Model on Bethe lattice
• Rigid colourings of hypergraphs and contiguity
• Low Auto-correlation Binary Sequences explored using Warning Propagation
• Cavity approach for modeling and fitting polymer stretching
• Identifying all irreducible conserved metabolite pools in genome-scale metabolic networks: a general method and the case of Escherichia coli