Statistical physics of hard combinatorial optimization: The vertex cover problem
arXiv:1404.6049 · doi:10.1088/1674-1056/23/7/078901
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 (10)
- Glassy dynamics of kinetically constrained models
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Minimum k-path vertex cover
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Core percolation on complex networks
- Immunization of Real Complex Communication Networks
- Message passing for vertex covers
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Ground-State Entropy of the Random Vertex-Cover Problem