Polynomial iterative algorithms for coloring and analyzing random graphs.

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 with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c in [c(d),c(q)].

• Publication year

  2003

• Venue

  Physical review. E, Statistical, nonlinear, and soft matter physics

• Publication date

  2003-04-24

• Fields of study

  Mathematics, Physics, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.68.036702arXiv cond-mat/0304558PMID 14524921
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Spin Glasses: A Challenge for Mathematicians.: A Challenge for Mathematicians.

  2005cited by this paper
• Coloring random graphs

  2002cited by this paper
• The Cavity Method at Zero Temperature

  2002cited by this paper
• Microscopic description of aging dynamics: fluctuation-dissipation relations, effective temperature, and heterogeneities.

  2002cited by this paper
• Random graph coloring: statistical physics approach.

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• Frozen development in graph coloring

  2001cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• Simplest random K-satisfiability problem

  2000cited by this paper
• Computational complexity for physicists

  2000cited by this paper
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs

  2000cited by this paper
• A Note on the Non-Colorability Threshold of a Random Graph

  2000cited by this paper
• Replica Symmetry Breaking in Short-Range Spin Glasses: Theoretical Foundations and Numerical Evidences

  1999cited by this paper
• A gap between the appearances of a k‐core and a (k + 1)‐chromatic graph

  1996cited by this paper
• Statistical Mechanics of the K--Satisfiability Model

  1996cited by this paper
• Sudden Emergence of a Giantk-Core in a Random Graph

  1996cited by this paper
• Weight space structure and internal representations: A direct approach to learning and generalization in multilayer neural networks.

  1995cited by this paper
• Structural glass transition and the entropy of the metastable states.

  1995cited by this paper
• Algorithms

  1992cited by this paper
• The chromatic number of random graphs

  1991cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• Graph optimisation problems and the Potts glass

  1987cited by this paper
• Spin glasses: Experimental facts, theoretical concepts, and open questions

  1986cited by this paper
• The Potts model

  1982cited by this paper
• Register Allocation Via Coloring

  1981cited by this paper
• Computers and In stractability: A Guide to the Theory of NP-Completeness. W. H Freeman, San Fran

  1979cited by this paper
• Every planar map is four colorable. Part II: Reducibility

  1977cited by this paper
• Complexity of Computer Computations

  1972cited by this paper

• On the atypical solutions of the symmetric binary perceptron

  2023cites this paper
• New Message Passing Methods for Min-Max and Sum-Product Inference

  2018cites this paper
• InSPIRES: a science shop project

  2017cites this paper
• Quantum cluster variational method and message passing algorithms revisited

  2017cites this paper
• Low Auto-correlation Binary Sequences explored using Warning Propagation

  2017cites this paper
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model

  2017cites this paper
• Analysing Survey Propagation Guided Decimation on Random Formulas

  2016cites this paper
• The replica symmetric solution for orthogonally constrained Heisenberg model on Bethe lattice

  2016cites this paper
• Fast inference of ill-posed problems within a convex space

  2016cites this paper
• Survey Propagation beyond Constraint Satisfaction Problems

  2016cites this paper
• Circular coloring of random graphs: statistical physics investigation

  2016cites this paper
• The Condensation Phase Transition in Random Graph Coloring

  2015cites this paper
• Sparse Probabilistic Models - Phase Transitions and Solutions via Spatial Coupling

  2015cites this paper
• Topics in Chromatic Graph Theory: Colouring random graphs

  2015cites this paper
• Message Passing and Combinatorial Optimization

  2015cites this paper
• A positive temperature phase transition in random hypergraph 2-coloring

  2014cites this paper
• Message passing and Monte Carlo algorithms: Connecting fixed points with metastable states

  2014cites this paper
• Perturbed message passing for constraint satisfaction problems

  2014cites this paper
• The Condensation Phase Transition in Random Graph Coloring

  2014cites this paper
• On the chromatic number of random regular graphs

  2013cites this paper
• Efficient algorithm for routing optimization via statistical mechanics

  2013cites this paper
• Perturbation Biology: Inferring Signaling Networks in Cellular Systems

  2013cites this paper
• Chasing the K-Colorability Threshold

  2013cites this paper
• Replica cluster variational method: the replica symmetric solution for the 2D random bond Ising model

  2012cites this paper
• Appendix A: Symbols and Notations

  2012cites this paper
• Swarm Intelligence Techniques for Optimization and Management Tasks in Sensor Networks

  2012cites this paper
• Generalized Survey Propagation

  2011influential citation
• Stochastic optimization by message passing

  2011cites this paper
• Characterizing and improving generalized belief propagation algorithms on the 2D Edwards–Anderson model

  2011cites this paper
• Networking—a statistical physics perspective

  2011influential citation
• Antiferromagnetic Potts Model on the Erdős-Rényi Random Graph

  2011cites this paper
• On a class of distributed algorithms over networks and graphs

  2011cites this paper
• The Geometric Evolution of Random Graph Colorings

  2010cites this paper
• Distributed graph coloring: an approach based on the calling behavior of Japanese tree frogs

  2010cites this paper
• Clusters of resource consuming nodes in transportation networks

  2010cites this paper
• A Study of Tabu Search for Coloring Random 3-Colorable Graphs Around the Phase Transition

  2010cites this paper
• Optimal location of sources in transportation networks

  2010cites this paper
• Structure in Networks

  2010cites this paper
• Approximate Inference for Clusters in Solution Spaces

  2010cites this paper
• Probabilistic Techniques for Constraint Satisfaction Problems

  2009influential citation
• Emergence of algorithmically hard phases in transportation networks

  2009cites this paper
• Phase transitions in transportation networks with nonlinearities.

  2009cites this paper
• Decimation flows in constraint satisfaction problems

  2009cites this paper
• Modularity of Sparse Random Graphs

  2009cites this paper
• Statistical mechanics of steiner trees.

  2008cites this paper
• Statistical Physics of Hard Optimization Problems

  2008cites this paper
• Counting Solution Clusters in Graph Coloring Problems Using Belief Propagation

  2008cites this paper
• Is SP BP?

  2008influential citation
• Algorithmic Barriers from Phase Transitions

  2008cites this paper
• Survey Propagation as "Probabilistic Token Passing"

  2008cites this paper
• On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs

  2008cites this paper
• A rigorous analysis of the cavity equations for the minimum spanning tree

  2008cites this paper
• Critical phenomena in complex networks

  2007cites this paper
• Finite Energy Survey Propagation for Constraint Satisfaction Problems

  2007influential citation
• Minimizing unsatisfaction in colourful neighbourhoods

  2007cites this paper
• (Un)detectable cluster structure in sparse networks.

  2007cites this paper
• Is SP BP

  2007influential citation
• Efficient supervised learning in networks with binary synapses

  2007cites this paper
• On the chromatic number of random graphs

  2007cites this paper
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

  2007cites this paper
• On the Interpretation of Survey Propagation

  2007cites this paper
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions

  2007cites this paper
• Géométrie et inférence dans l'optimisation et en théorie de l'information

  2007cites this paper
• Is SP BP?

  2007influential citation
• Potts glass on random graphs

  2007cites this paper
• Zero temperature solutions of the Edwards-Anderson model in random Husimi lattices

  2007cites this paper
• A Spectral Approach to Analysing Belief Propagation for 3-Colouring

  2007cites this paper
• Phase Transitions in the Coloring of Random Graphs

  2007cites this paper
• Maximum independent set on diluted triangular lattices.

  2006cites this paper
• Message passing for vertex covers

  2006cites this paper
• Optimization using quantum mechanics: quantum annealing through adiabatic evolution

  2006cites this paper
• Statistical mechanics of optimization problems

  2006cites this paper
• The cavity method for large deviations

  2005cites this paper
• Deterministic and stochastic quantum annealing approaches

  2005cites this paper
• Reconstruction on Trees and Spin Glass Transition

  2005cites this paper
• Survey propagation at finite temperature: application to a Sourlas code as a toy model

  2005cites this paper
• Studies of Classical and Quantum Annealing

  2005cites this paper
• Learning by message-passing in networks of discrete synapses

  2005cites this paper
• Pairs of SAT Assignment in Random Boolean Formulae

  2005cites this paper
• Landscape of solutions in constraint satisfaction problems

  2005cites this paper
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models

  2005cites this paper
• Pairs of SAT Assignments and Clustering in Random Boolean Formulae

  2005cites this paper
• Clustering of solutions in the random satisfiability problem

  2005cites this paper
• Source coding by efficient selection of ground-state clusters.

  2004cites this paper
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

  2004cites this paper
• Extremal optimization at the phase transition of the three-coloring problem.

  2004cites this paper
• Near-optimal configurations in mean-field disordered systems.

  2003cites this paper
• Constraint Satisfaction by Survey Propagation

  2002cites this paper
• Cavity algorithms under global constraints: classical and quantum problems

  year unknowncites this paper
• N Ear Optim Al Congurations in M Ean Eld Disordered System S

  year unknowncites this paper