Minimal vertex covers on finite-connectivity random graphs: a hard-sphere lattice-gas picture.
The minimal vertex-cover (or maximal independent-set) problem is studied on random graphs of finite connectivity. Analytical results are obtained by a mapping to a lattice gas of hard spheres of (chemical) radius 1, and they are found to be in excellent agreement with numerical simulations. We give a detailed description of the replica-symmetric phase, including the size and entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c approximately 1.43. The replica-symmetric solution breaks down at c=e approximately 2.72. We give a simple one-step replica-symmetry-broken solution, and discuss the problems in the interpretation and generalization of this solution.
Weigt
M
M
Institute for Theoretical Physics, University of Göttingen, Bunsenstrasse 9, 37073 Göttingen, Germany. weigt@theorie.physik.uni-goettingen.de
Hartmann
A K
AK