Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture

Martin Weigt, Alexander K. Hartmann

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 h…