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

Abstract

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.

4 pages, 3 eps-figures, new version to be published in Phys. Rev. Let

Cited by in corpus (81)

• Evolution of networks
• Critical phenomena in complex networks
• Coloring random graphs
• Boosting search by rare events
• The number of matchings in random graphs
• Simplest random K-satisfiability problem
• Core percolation on complex networks
• Core percolation in random graphs: a critical phenomena analysis
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Exact solutions for diluted spin glasses and optimization problems
• Entropies of complex networks with hierarchically constrained topologies
• On adaptability and "intermediate phase" in randomly connected networks
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Covering Problems and Core Percolations on Hypergraphs
• Message passing for vertex covers
• Computational complexity arising from degree correlations in networks
• Distance-d covering problems in scale-free networks with degree correlations
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Generalization of core percolation on complex networks
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Controllability and maximum matchings of complex networks
• Random Graph Coloring - a Statistical Physics Approach
• Statistical mechanics of the vertex-cover problem
• Statistical Mechanics of maximal independent sets
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• The hard-core model on random graphs revisited
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• Near optimal configurations in mean field disordered systems
• Spin models on random graphs with controlled topologies beyond degree constraints
• Metastable configurations of spin models on random graphs
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• The cavity method for large deviations
• Core organization of directed complex networks
• RNA secondary structure design
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Numerical Solution-Space Analysis of Satisfiability Problems
• Approximate analysis of search algorithms with "physical" methods
• Ground-State Entropy of the Random Vertex-Cover Problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Phase transition for cutting-plane approach to vertex-cover problem
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• The stability to instability transition in the structure of large scale networks
• Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
• A hard-sphere model on generalized Bethe lattices: Statics
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Reversible adsorption on a random site surface
• Solution-space structure of (some) optimization problems
• Two faces of greedy leaf removal procedure on graphs
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
• Optimal Location of Sources in Transportation Networks
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Statistical Physics of Group Testing
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Typical Approximation Performance for Maximum Coverage Problem
• A hard-sphere model on generalised Bethe lattices: Dynamics
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• A residual-based message passing algorithm for constraint satisfaction problems
• An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Computational Complexity for Physicists
• Counting Complex Disordered States by Efficient Pattern Matching: Chromatic Polynomials and Potts Partition Functions
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Optimal Vertex Cover for the Small-World Hanoi Networks
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Phase transition in the bipartite z-matching
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks
• Statistical mechanics of the minimum vertex cover problem in stochastic block models