Typical Solution Time for a Vertex-Covering Algorithm on Finite-Connectivity Random Graphs
- 19 February 2001
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 86 (8), 1658-1661
- https://doi.org/10.1103/physrevlett.86.1658
Abstract
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 an algorithm-independent phase transition in its solvability. Analytical results are corroborated by numerical simulations.Other Versions
This publication has 10 references indexed in Scilit:
- Trajectories in Phase Diagrams, Growth Processes, and Computational Complexity: How Search Algorithms Solve the 3-Satisfiability ProblemPhysical Review Letters, 2001
- Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random GraphsPhysical Review Letters, 2000
- Determining computational complexity from characteristic ‘phase transitions’Nature, 1999
- Phase Transition in the Number Partitioning ProblemPhysical Review Letters, 1998
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- On the independence number of random graphsDiscrete Mathematics, 1990
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability ProblemSIAM Journal on Computing, 1986
- Independent sets in random sparse graphsNetworks, 1984
- Finding a Maximum Independent SetSIAM Journal on Computing, 1977
- Branch-and-Bound Methods: A SurveyOperations Research, 1966