Number of guards needed by a museum: A phase transition in vertex coveringof random graphs

In this Letter we study the NP-complete vertex cover problem on finite conn ectivity random graphs. When the allowed size of the cover set is decreased , a discontinuous transition in solvability and typical-case complexity occ urs. This transition is characterized by means of exact numerical simulatio ns as well as by analytical replica calculations. The replica symmetric pha se diagram is in excellent agreement with numerical findings up to average connectivity e, where replica symmetry becomes locally unstable.