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

Alexander K. Hartmann, Martin Weigt

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 fou…