The number of guards needed by a museum: A phase transition in vertex covering of random graphs

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.

• Publication year

  2000

• Venue

  Physical Review Letters

• Publication date

  2000-01-11

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevLett.84.6118arXiv cond-mat/0001137PMID 10991138
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Mean-field theory of spin-glasses with finite coordination number.

  1987cited by this paper

• Long-range frustration in Minimal Vertex Cover Problem on random graphs

  2025cites this paper
• Bayesian Game for Distributed Weighted K-Path Vertex Cover of Dynamic Networks

  2025cites this paper
• Counting and hardness-of-finding fixed points in cellular automata on random graphs

  2024cites this paper
• Nonuniversality for crossword puzzle percolation.

  2024cites this paper
• Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances

  2024cites this paper
• Simulated annealing, optimization, searching for ground states

  2023cites this paper
• Effect of constraint relaxation on the minimum vertex cover problem in random graphs.

  2023cites this paper
• Planted vertex cover problem on regular random graphs and nonmonotonic temperature-dependence in the supercooled region.

  2023cites this paper
• Cutting-plane algorithms and solution whitening for the vertex-cover problem.

  2022cites this paper
• A residual-based message passing algorithm for constraint satisfaction problems

  2022cites this paper
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks

  2022cites this paper
• The Nature of Complex Networks

  2022cites this paper
• Easy-hard phase transition in parameter estimation for optical waveguides

  2020cites this paper
• Covering Problems and Core Percolations on Hypergraphs.

  2020cites this paper
• A Smart Approximation Algorithm for Minimum Vertex Cover Problem based on Min-to-Min (MtM) Strategy

  2020cites this paper
• Hierarchical Decomposition Mechanism by König-Egérvary Layer-Subgraph with Application on Vertex-Cover

  2019cites this paper
• Statistical mechanics of the minimum vertex cover problem in stochastic block models.

  2019cites this paper
• Two faces of greedy leaf removal procedure on graphs

  2018influential citation
• Core structure: The coupling failure procedure in multiplex networks

  2018cites this paper
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

  2018cites this paper
• The $z$-matching problem on bipartite graphs

  2018cites this paper
• Controllability and maximum matchings of complex networks

  2018cites this paper
• Constructing concrete hard instances of the maximum independent set problem

  2018cites this paper
• A local algorithm and its percolation analysis of bipartite z-matching problem

  2018cites this paper
• Generalization of core percolation on complex networks.

  2018cites this paper
• Typical Approximation Performance for Maximum Coverage Problem

  2017cites this paper
• Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming

  2017cites this paper
• Fault Tolerance of Random Graphs with respect to Connectivity: Phase Transition in Logarithmic Average Degree

  2017cites this paper
• Uncertain programming model for uncertain minimum weight vertex covering problem

  2017cites this paper
• A Simple, Fast and Near Optimal Approximation Algorithm for Optimization of Un-Weighted Minimum Vertex Cover

  2016cites this paper
• Analytical solution for the size of the minimum dominating set in complex networks

  2016cites this paper
• Typical performance of approximation algorithms for NP-hard problems

  2016cites this paper
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems

  2016cites this paper
• Structure and controllability of complex networks

  2015cites this paper
• Clever Steady Strategy Algorithm: A Simple and Efficient Approximation Algorithm for Minimum Vertex Cover Problem

  2015cites this paper
• ALBERT-LÁSZLÓ BARABÁSI NETWORK SCIENCE

  2015cites this paper
• Research on solution space of bipartite graph vertex-cover by maximum matchings

  2015cites this paper
• Uncertain programming model for uncertain minimum weight vertex covering problem

  2014cites this paper
• Statistical physics of hard combinatorial optimization: Vertex cover problem

  2014cites this paper
• Research of the Minimum Vertex-Cover Solutions on the Tree and Lattice Structures

  2014cites this paper
• Evaluating Locality Sensitive Hashing for Matching Partial Image Patches in a Social Media Setting

  2014cites this paper
• Investigating Facebook Groups through a Random Graph Model

  2014cites this paper
• Organization mechanism and counting algorithm on vertex-cover solutions

  2014cites this paper
• Edge orientation for optimizing controllability of complex networks.

  2014cites this paper
• Connecting Core Percolation and Controllability of Complex Networks

  2014cites this paper
• Complete set of types of phase transition in generalized heterogeneous k-core percolation.

  2014cites this paper
• A greedy approach based algorithm for the vertex cover problem

  2013cites this paper
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective

  2013cites this paper
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm.

  2013cites this paper
• The hard-core model on random graphs revisited

  2013cites this paper
• Core organization of directed complex networks

  2012cites this paper
• Core percolation on complex networks

  2012cites this paper
• Phase transition for cutting-plane approach to vertex-cover problem

  2012cites this paper
• Measuring instance difficulty for combinatorial optimization problems

  2012cites this paper
• Stability-to-instability transition in the structure of large-scale networks.

  2012cites this paper
• Detecting the solution space of vertex cover by mutual determinations and backbones.

  2011cites this paper
• Optimal vertex cover for the small-world Hanoi networks.

  2011cites this paper
• Topological Optimization in Network Dynamical Systems

  2011influential citation
• Optimal location of sources in transportation networks

  2010cites this paper
• A Meta-Heuristic Algorithm for Vertex Covering Problem Based on Gravity

  2010cites this paper
• Numerical solution-space analysis of satisfiability problems.

  2010cites this paper
• Optimization of Unweighted Minimum Vertex Cover

  2010cites this paper
• Optimization of Unweighted Minimum

  2010cites this paper
• Clusters of resource consuming nodes in transportation networks

  2010cites this paper
• An Effective Algorithm for Minimum Weighted Vertex Cover Problem

  2010cites this paper
• Structure in Networks

  2010cites this paper
• Complete Algorithms on Minimum Vertex -Cover

  2009cites this paper
• Counting complex disordered states by efficient pattern matching: chromatic polynomials and Potts partition functions

  2009cites this paper
• Phase transitions in transportation networks with nonlinearities.

  2009cites this paper
• A First Principles Approach to Block Structure Detection

  2009cites this paper
• Emergence of algorithmically hard phases in transportation networks

  2009cites this paper
• Statistical mechanics of maximal independent sets.

  2009cites this paper
• Statistical mechanics of the quantum K -satisfiability problem.

  2008cites this paper
• Ground-state entropy of the random vertex-cover problem.

  2008cites this paper
• Spin models on random graphs with controlled topologies beyond degree constraints

  2008cites this paper
• Entropies of complex networks with hierarchically constrained topologies.

  2008cites this paper
• Equilibrium adsorption on a random site surface.

  2008cites this paper
• Statistical physics of group testing

  2007cites this paper
• Statistical mechanics of the hitting set problem.

  2007cites this paper
• Zero temperature solutions of the Edwards-Anderson model in random Husimi lattices

  2007cites this paper
• Dynamical replica analysis of processes on finitely connected random graphs: I. Vertex covering

  2007cites this paper
• Solution-space structure of (some) optimization problems

  2007cites this paper
• Hybrid evolutionary algorithms on minimum vertex cover for random graphs

  2007cites this paper
• Cyclic Heating-Annealing and Boltzmann Distribution of Free Energies in a Spin-Glass System

  2007cites this paper
• Critical phenomena in complex networks

  2007influential citation
• Message passing for vertex covers

  2006cites this paper
• RNA secondary structure design.

  2006cites this paper
• Optimization using quantum mechanics: quantum annealing through adiabatic evolution

  2006cites this paper
• Maximum independent set on diluted triangular lattices.

  2006cites this paper
• Reversible adsorption on a random site surface

  2006cites this paper
• Phase Transition In Random SAT Problems

  2006cites this paper
• The number of matchings in random graphs

  2006cites this paper
• The cavity method for large deviations

  2005cites this paper
• Phase transition and finite-size scaling in the vertex-cover problem

  2005cites this paper
• Aprendizado em Modelos de Markov com Variáveis de Estado Escondidas

  2005cites this paper
• Deterministic and stochastic quantum annealing approaches

  2005cites this paper
• A hard-sphere model on generalized Bethe lattices: dynamics

  2005cites this paper
• A hard-sphere model on generalized Bethe lattices: statics

  2005cites this paper
• Studies of Classical and Quantum Annealing

  2005cites this paper
• Adaptability and "intermediate phase" in randomly connected networks.

  2004cites this paper