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