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

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\ll 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}(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.