Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs

We analytically describe the typical solution time needed by a backtracking algorithm to solve the vertex-cover problem on finite-connectivity random graphs. We find two different transitions: The first one is algorithm depen dent and marks the dynamical transition from linear to exponential solution times. The second one gives the maximum computational complexity, and is f ound exactly at the threshold where the system undergoes an algorithm-indep endent phase transition in its solvability. Analytical results are corrobor ated by numerical simulations.