The typical-case complexity of a vertex-covering algorithm on finite-connectivity random graphs
Abstract
In this letter, 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-dependent and marks the dynamical transition from linear to exponential solution times. The second one gives the maximum computational complexity, and is found exactly at the threshold where the system undergoes a phase transition in its solvability. Its location consequently does not depend on the details of the chosen algorithm. The analytical results are corroborated by numerical simulations.Keywords
All Related Versions
This publication has 0 references indexed in Scilit: