Dynamics of heuristic optimization algorithms on random graphs

Abstract

In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed. In every algorithmic step, a vertex is chosen with respect to its vertex degree. This vertex, and some environment of it, is covered and removed from the graph. This graph reduction process can be described as a Markovian dynamics in the space of random graphs of arbitrary degree distribution. We discuss some solvable cases, including algorithms already analysed using different techniques, and develop approximation schemes for more complicated cases. The approximations are corroborated by numerical simulations.

19 pages, 3 figures, version to app. in EPJ B

Cited by in corpus (14)

• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Message passing for vertex covers
• Computational complexity arising from degree correlations in networks
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Generalization of core percolation on complex networks
• Statistical mechanics of the vertex-cover problem
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Core organization of directed complex networks
• Approximate analysis of search algorithms with "physical" methods
• Approximating satisfiability transition by suppressing fluctuations
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Typical Approximation Performance for Maximum Coverage Problem
• Feedback topology and XOR-dynamics in Boolean networks with varying input structure