Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity random graphs
| dc.creator | Hartmann, Alexander K. | |
| dc.creator | Weigt, Martin | |
| dc.date | 2000-06-21 | |
| dc.date.accessioned | 2026-07-07T02:37:58Z | |
| dc.date.available | 2026-07-07T02:37:58Z | |
| dc.description | 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. | |
| dc.description | 24 pages, 9 figures | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0006316 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0006316 | |
| dc.identifier | Theoretical Computer Science 265, 199 (2001) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/16498 | |
| dc.subject | Statistical Mechanics | |
| dc.subject | Computational Complexity | |
| dc.title | Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity random graphs | |
| dc.type | text |