%0 Book Section %1 statphys23_0135 %A Zdeborova, L. %A Krzakala, F. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K cavity computational constraint hardness method phase problems satisfaction statphys23 topic-2 transitions %T Phase transitions in random graph coloring revisited %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=135 %X One of the most challenging constraint satisfaction problems is to color the vertices of a large sparse random graph with a given number of colors in such a way that no adjacent vertices have the same color. Using the cavity method, we present a systematic study of the space of proper colorings for different random graphs ensembles and numbers of colors. We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those happening in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states. Subsequently, it condensates over a finite number of the largest states. Another transition takes place when in all the dominant states a finite fraction of nodes freezes, i.e. each of these nodes takes a single color in all the solutions belonging to the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs. Finally, we discuss the algorithmic consequences of our findings, and argue in particular that the clustering transition is not associated with the onset of computational hardness. We show the performance of a simple local search Walk-COL algorithm, and of the Belief Propagation algorithm, which is an efficient tool to find and count solutions until (at least) the condensation transition. We conjecture that it is instead the freezing transition which is relevant candidate to explain the onset of the computational hardness.

@incollection{statphys23_0135, abstract = {One of the most challenging constraint satisfaction problems is to color the vertices of a large sparse random graph with a given number of colors in such a way that no adjacent vertices have the same color. Using the cavity method, we present a systematic study of the space of proper colorings for different random graphs ensembles and numbers of colors. We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those happening in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states. Subsequently, it condensates over a finite number of the largest states. Another transition takes place when in all the dominant states a finite fraction of nodes freezes, i.e. each of these nodes takes a single color in all the solutions belonging to the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs. Finally, we discuss the algorithmic consequences of our findings, and argue in particular that the clustering transition is not associated with the onset of computational hardness. We show the performance of a simple local search Walk-COL algorithm, and of the Belief Propagation algorithm, which is an efficient tool to find and count solutions until (at least) the condensation transition. We conjecture that it is instead the freezing transition which is relevant candidate to explain the onset of the computational hardness.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Zdeborova, L. and Krzakala, F.}, biburl = {https://www.bibsonomy.org/bibtex/2644b479f49dfb454351956346d8e214f/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {7bae2757a7e8fea9107040b0eff6688c}, intrahash = {644b479f49dfb454351956346d8e214f}, keywords = {cavity computational constraint hardness method phase problems satisfaction statphys23 topic-2 transitions}, month = {9-13 July}, timestamp = {2007-06-20T10:16:12.000+0200}, title = {Phase transitions in random graph coloring revisited}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=135}, year = 2007 }