2000/01/31 by Martin Weigt, Alexander K. Hartmann · 212 citations
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Computer science #Cover (algebra) #Discrete mathematics #Graph #Markov Chains and Monte Carlo Methods #Mathematics #Phase (matter) #Phase diagram #Phase transition #Physics #Quantum mechanics #Random graph #Replica #Set (abstract data type) #Statistical physics #Stochastic processes and statistical mechanics #Symmetry breaking #Theoretical and Computational Physics #Vertex (graph theory) #Vertex cover #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.1103/physrevlett.84.6118
published in Physical Review Letters 84(26), 6118-6121 (American Physical Society) · 4 pages, 3 eps-figures, new version to be published in Phys. Rev. Let
arxiv created 2000/05/03 · openalex publication_date 2000/06/26 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this Letter we study the NP-complete vertex cover problem on finite connectivity random graphs. When the allowed size of the cover set is decreased, a discontinuous transition in solvability and typical-case complexity occurs. This transition is characterized by means of exact numerical simulations as well as by analytical replica calculations. The replica symmetric phase diagram is in excellent agreement with numerical findings up to average connectivity e, where replica symmetry becomes locally unstable.