Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity random graphs
<|reference_start|>Statistical mechanics perspective on the phase transition in vertex covering 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\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 the critical backbone size $b_c(c)$ 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.<|reference_end|>
@article{hartmann2000statistical,
    title={Statistical mechanics perspective on the phase transition in vertex
  covering finite-connectivity random graphs},
    author={Alexander K. Hartmann and Martin Weigt},
    journal={Theoretical Computer Science 265, 199 (2001)},
    year={2000},
    archivePrefix={arXiv},
    eprint={cond-mat/0006316},
    primaryClass={cond-mat.stat-mech cs.CC}
}