Polynomial iterative algorithms for coloring and analyzing 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. Furthermore, we extended our considerations to the case of single instances showing consistent results. This lead us to propose a new algorithm able to color in polynomial time random graphs in the hard but colorable region, i.e when $c\in [c_d,c_q]$.

23 pages, 10 eps figures

References in corpus (11)

• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• Replica Symmetry Breaking in Short-Range Spin Glasses: Theoretical Foundations and Numerical Evidences
• Coloring random graphs
• Simplest random K-satisfiability problem
• Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network
• Random Graph Coloring - a Statistical Physics Approach
• A microscopic description of the aging dynamics: fluctuation-dissipation relations, effective temperature and heterogeneities

Cited by in corpus (47)

• Critical phenomena in complex networks
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• Perturbation Biology: inferring signaling networks in cellular systems
• Algorithmic barriers from phase transitions
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Learning by message-passing in networks of discrete synapses
• Efficient supervised learning in networks with binary synapses
• 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
• (Un)detectable cluster structure in sparse networks
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Message passing for vertex covers
• Pairs of SAT Assignment in Random Boolean Formulae
• Statistical Mechanics of Steiner trees
• Networking - A Statistical Physics Perspective
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• Potts Glass on Random Graphs
• The condensation phase transition in random graph coloring
• A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
• Near optimal configurations in mean field disordered systems
• A rigorous analysis of the cavity equations for the minimum spanning tree
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• Stochastic optimization by message passing
• The cavity method for large deviations
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Antiferromagnetic Potts model on the Erdos-Renyi random graph
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Source coding by efficient selection of ground states clusters
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Fast inference of ill-posed problems within a convex space
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Optimal Location of Sources in Transportation Networks
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• The effect of quantum fluctuations on the coloring of random graphs
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• Decimation flows in constraint satisfaction problems
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• Perturbed Message Passing for Constraint Satisfaction Problems
• Statistical mechanics of optimization problems
• Low Auto-correlation Binary Sequences explored using Warning Propagation
• The replica symmetric solution for Orthogonally Constrained Heisenberg Model on Bethe lattice