https://doi.org/10.1140/epjb/e2003-00096-4
Vertex cover problem studied by cavity method: Analytics and population dynamics
Max-Planck-Institute of Colloids and Interfaces,
14424 Potsdam, Germany
Corresponding author: a zhou@mpikg-golm.mpg.de
Received:
11
November
2002
Published online:
1
April
2003
We study the vertex cover problem on finite connectivity random graphs by zero-temperature cavity method. The minimum vertex cover corresponds to the ground state(s) of a proposed Ising spin model. When the connectivity c > e=2.718282, there is no state for this system as the reweighting parameter y, which takes a similar role as the inverse temperature β in conventional statistical physics, approaches infinity; consequently the ground state energy is obtained at a finite value of y when the free energy function attains its maximum value. The minimum vertex cover size at given c is estimated using population dynamics and compared with known rigorous bounds and numerical results. The backbone size is also calculated.
PACS: 75.10.Nr – Spin-glass and other random models / 89.75.-k – Complex systems / 05.20.-y – Classical statistical mechanics
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2003