Statistical mechanics of the vertex-cover problem

Abstract

We review recent progress in the study of the vertex-cover problem (VC). VC belongs to the class of NP-complete graph theoretical problems, which plays a central role in theoretical computer science. On ensembles of random graphs, VC exhibits an coverable-uncoverable phase transition. Very close to this transition, depending on the solution algorithm, easy-hard transitions in the typical running time of the algorithms occur. We explain a statistical mechanics approach, which works by mapping VC to a hard-core lattice gas, and then applying techniques like the replica trick or the cavity approach. Using these methods, the phase diagram of VC could be obtained exactly for connectivities $c<e$, where VC is replica symmetric. Recently, this result could be confirmed using traditional mathematical techniques. For $c>e$, the solution of VC exhibits full replica symmetry breaking. The statistical mechanics approach can also be used to study analytically the typical running time of simple complete and incomplete algorithms for VC. Finally, we describe recent results for VC when studied on other ensembles of finite- and infinite-dimensional graphs.

review article, 26 pages, 9 figures, to appear in J. Phys. A: Math. Gen

References in corpus (32)

• The Bethe lattice spin glass revisited
• 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
• Lattice Glass Models
• Boosting search by rare events
• A ``Tetris''-like model for the Compaction of Dry Granular Media
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• A variational description of the ground state structure in random satisfiability problems
• Simplest random K-satisfiability problem
• A ferromagnet with a glass transition
• Core percolation in random graphs: a critical phenomena analysis
• Exact solutions for diluted spin glasses and optimization problems
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Aging and multiscaling in out of equilibrium dynamical processes in granular media
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Computational complexity arising from degree correlations in networks
• Tapping Spin Glasses
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Entropy of particle packings : an illustration on a toy model
• Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
• Two time scales and FDT violation in a Finite Dimensional Model for Structural Glasses
• Higher-order QED corrections to single-W production in electron-positron collisions
• The jamming transition of Granular Media
• Glassy dynamics near zero temperature
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• Response properties in a model for granular matter
• On random graphs and the statistical mechanics of granular matter
• Glassy behavior of the site frustrated percolation model
• Dynamics of heuristic optimization algorithms on random graphs
• Dynamics of the frustrated Ising lattice gas
• Phase transitions in the steady state behavior of mechanically perturbed spin glasses and ferromagnets
• On Lattice Gas Models For Disordered Systems

Cited by in corpus (23)

• Core percolation on complex networks
• Avalanches in mean-field models and the Barkhausen noise in spin-glasses
• Covering Problems and Core Percolations on Hypergraphs
• Statistical Mechanics of the Minimum Dominating Set Problem
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• The hard-core model on random graphs revisited
• Clustering analysis of the ground-state structure of the vertex-cover problem
• A frozen glass phase in the multi-index matching problem
• The cavity method for large deviations
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• Parallel Tempering for the planted clique problem
• Properties of atypical graphs from negative complexities
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Solution-space structure of (some) optimization problems
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Two faces of greedy leaf removal procedure on graphs
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Percolation of satisfiability in finite dimensions
• Minimal vertex covers of random trees
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Gradient dynamics in reinforcement learning