How many guards needs a museum - an easy-hard transition in vertex covering of random graphs

In this letter we study the NP-complete vertex cover problem on finite connectivity random graphs. When the allowed size of the cover set is decreased a discontinuous transition in solvability occurs and, even more importantly, in its typical case complexity. This transition is characterized as well by means of exact numerical simulations as of analytical replica calculations. The values for the threshold and the backbone are calculated in dependence on the average connectivity of the graph. The results of the replica symmetric approach are in excellent agreement with numerical findings up to an average connectivity $e$, where they are therefore conjectured to be exact. At connectivity $e$, an instability of the simple replica symmetric solution occurs.