Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture - art. no. 056127

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 a nd entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c similar or equal to 1.43. The replica-symmetric solution breaks down at c = e similar or equ al to 2.72. We give a simple one-step replica-symmetry-broken solution, and discuss the problems in the interpretation and generalization of this solu tion.