Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

The vertex-cover problem is studied for random graphs G(N,cN) having N vertices and cN edges. Exact numerical results are obtained by a branch-and-bound algorithm. It is found that a transition in the coverability at a c-dependent threshold x = x(c)(c) appears, where xN is the cardinality of the vertex cover. This transition coincides with a sharp peak of the typical numerical effort, which is needed to decide whether there exists a cover with xN vertices or not. For small edge concentrations c much less than 0.5, a cluster expansion is performed, giving very accurate results in this regime. These results are extended using methods developed in statistical physics. The so-called annealed approximation reproduces a rigorous bound on x(c)(c) which was known previously. The main part of the paper contains an application of the replica method. Within the replica symmetric ansatz the threshold x,(c) and various statistical properties of minimal vertex covers can be calculated. For c < e/2 the results show an excellent agreement with the numerical findings. At average vertex degree 2c = e, an instability of the simple replica symmetric solution occurs. (C) 2001 Elsevier Science B.V. All rights reserved.