Polynomial iterative algorithms for coloring and analyzing random graphs

A. Braunstein , R. Mulet , A. Pagnani (1) , M. Weigt , R. Zecchina

1 LPTMS - Laboratoire de Physique Théorique et Modèles Statistiques

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∈[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∈[c_d,c_q].

Mots clés: Computational techniques; simulations; Computer science and technology; Spin-glass and other random models; Phase transitions: general studies; Condensed Matter - Disordered Systems and Neural Networks; Condensed Matter - Statistical Mechanics; 02.70.-c; 89.20.Ff; 75.10.Nr; 05.70.Fh

Domaines: Planète et Univers [physics]

A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, R. Zecchina. Polynomial iterative algorithms for coloring and analyzing random graphs. Physical Review E , 2003, 68, ⟨10.1103/PhysRevE.68.036702⟩. ⟨insu-03726414⟩