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 vert ices and cN edges. Exact numerical results are obtained by a branch-and-bou nd algorithm. It is found that a transition in the coverability at a c-depe ndent threshold x = x(c)(c) appears, where xN is the cardinality of the ver tex cover. This transition coincides with a sharp peak of the typical numer ical 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 clu ster expansion is performed, giving very accurate results in this regime. T hese results are extended using methods developed in statistical physics. T he so-called annealed approximation reproduces a rigorous bound on x(c)(c) which was known previously. The main part of the paper contains an applicat ion of the replica method. Within the replica symmetric ansatz the threshol d 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 nu merical findings. At average vertex degree 2c = e, an instability of the si mple replica symmetric solution occurs. (C) 2001 Elsevier Science B.V. All rights reserved.