2003/07/10 by Alexander K. Hartmann, Martin Weigt · 36 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Combinatorics #Computer science #Cover (algebra) #Data Management and Algorithms #Engineering #Graph #Markov Chains and Monte Carlo Methods #Mathematics #Mechanical engineering #Physics #Statistical mechanics #Statistical physics #Topological and Geometric Data Analysis #Vertex (graph theory) #Vertex cover #cond-mat.dis-nn
paper · pdf · doi:10.1088/0305-4470/36/43/028
published in Journal of Physics A Mathematical and General 36(43), 11069-11093 (Institute of Physics) · review article, 26 pages, 9 figures, to appear in J. Phys. A: Math. Gen
arxiv created 2003/07/10 · openalex publication_date 2003/10/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We review recent progress in the study of the vertex-cover problem (VC). The 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 a 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 the VC to a hard-core lattice gas, and then applying techniques such as the replica trick or the cavity approach. Using these methods, the phase diagram of the VC could be obtained exactly for connectivities c < e , where the VC is replica symmetric. Recently, this result could be confirmed using traditional mathematical techniques. For c > e , the solution of the 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 the VC. Finally, we describe recent results for the VC when studied on other ensembles of finite- and infinite-dimensional graphs.