Statistical physics of hard combinatorial optimization: The vertex cover problem

Abstract

Typical-case computation complexity is a research topic at the boundary of computer science, applied mathematics, and statistical physics. In the last twenty years the replica-symmetry-breaking mean field theory of spin glasses and the associated message-passing algorithms have greatly deepened our understanding of typical-case computation complexity. In this paper we use the vertex cover problem, a basic nondeterministic-polynomial (NP)-complete combinatorial optimization problem of wide application, as an example to introduce the statistical physical methods and algorithms. We do not go into the technical details but emphasize mainly the intuitive physical meanings of the message-passing equations. A nonfamiliar reader shall be able to understand to a large extent the physics behind the mean field approaches and to adjust them in solving other optimization problems.

17 pages. A mini-review to be published in Chinese Physics B

References in corpus (35)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Simulated Tempering: A New Monte Carlo Scheme
• The Bethe lattice spin glass revisited
• Glassy dynamics of kinetically constrained models
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• Coloring random graphs
• Minimum k-path vertex cover
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• The number of matchings in random graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Core percolation on complex networks
• Core percolation in random graphs: a critical phenomena analysis
• Exact solutions for diluted spin glasses and optimization problems
• Spin glass approach to the feedback vertex set problem
• Immunization of Real Complex Communication Networks
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Message passing for vertex covers
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Random Graph Coloring - a Statistical Physics Approach
• Statistical mechanics of the vertex-cover problem
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Statistical Mechanics of maximal independent sets
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• The network source location problem: ground state energy, entropy and effects of freezing

Cited by in corpus (8)

• Statistical Mechanics of the Minimum Dominating Set Problem
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Two faces of greedy leaf removal procedure on graphs
• Maximally flexible solutions of a random $K$-satisfiability formula
• Spin-glass model for the C-dismantling problem
• Typical Performance of Approximation Algorithms for NP-hard Problems
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Statistical mechanics of the minimum vertex cover problem in stochastic block models