Typical solution time for 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 an algorithm-independent phase transition in its solvability. Analytical results are corroborated by numerical simulations.

4 pages, 2 figures, to appear in Phys. Rev. Lett

References in corpus (2)

• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem

Cited by in corpus (27)

• Statistical mechanics of complex networks
• Evolution of networks
• Boosting search by rare events
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Statistical mechanics of the vertex-cover problem
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• Statistical Mechanics of an NP-complete Problem: Subset Sum
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Approximate analysis of search algorithms with "physical" methods
• Phase transition for cutting-plane approach to vertex-cover problem
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• The dynamics of proving uncolourability of large random graphs I. Symmetric Colouring Heuristic
• Two faces of greedy leaf removal procedure on graphs
• Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Restart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm
• Phase transition in the bipartite z-matching
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers
• Statistical mechanical models of integer factorization problem