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.

Keywords

All Related 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 Problem
Physical Review Letters, 2001
Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs
Physical Review Letters, 2000
Determining computational complexity from characteristic ‘phase transitions’
Nature, 1999
Phase Transition in the Number Partitioning Problem
Physical Review Letters, 1998
Statistical mechanics of the random $K$ -satisfiability model
Physical Review E, 1997
On the independence number of random graphs
Discrete Mathematics, 1990
Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
SIAM Journal on Computing, 1986
Independent sets in random sparse graphs
Networks, 1984
Finding a Maximum Independent Set
SIAM Journal on Computing, 1977
Branch-and-Bound Methods: A Survey
Operations Research, 1966