Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture

Abstract

The minimal vertex-cover (or maximal independent-set) problem is studied on random graphs of finite connectivity. Analytical results are obtained by a mapping to a lattice gas of hard spheres of (chemical) radius one, and they are found to be in excellent agreement with numerical simulations. We give a detailed description of the replica-symmetric phase, including the size and the entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at connectivity $c\simeq 1.43$. The replica-symmetric solution breaks down at $c=e\simeq 2.72$. We give a simple one-step replica symmetry broken solution, and discuss the problems in interpretation and generalization of this solution.

32 pages, 9 eps figures, to app. in PRE (01 May 2001)

References in corpus (9)

• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• A variational description of the ground state structure in random satisfiability problems
• Simplest random K-satisfiability problem
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Two time scales and FDT violation in a Finite Dimensional Model for Structural Glasses
• Glassy dynamics near zero temperature
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• Response properties in a model for granular matter

Cited by in corpus (52)

• Critical phenomena in complex networks
• Lattice Glass Models
• Boosting search by rare events
• Glass models on Bethe lattices
• Core percolation in random graphs: a critical phenomena analysis
• 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
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
• Random Graph Coloring - a Statistical Physics Approach
• Statistical mechanics of the vertex-cover problem
• Statistical Mechanics of maximal independent sets
• The hard-core model on random graphs revisited
• A microscopic description of the aging dynamics: fluctuation-dissipation relations, effective temperature and heterogeneities
• Quantum Sampling Algorithms for Near-Term Devices
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• 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
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Approximate analysis of search algorithms with "physical" methods
• Ground-State Entropy of the Random Vertex-Cover Problem
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• On the phase transitions of graph coloring and independent sets
• Pseudoknots in a Homopolymer
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Properties of atypical graphs from negative complexities
• Reversible adsorption on a random site surface
• Solution-space structure of (some) optimization problems
• Two faces of greedy leaf removal procedure on graphs
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Optimal Location of Sources in Transportation Networks
• Statistical Physics of Group Testing
• Spin-glass model for the C-dismantling problem
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• 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
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Optimal Vertex Cover for the Small-World Hanoi Networks
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem
• Phase transition in the bipartite z-matching
• Vertex-cover in random graphs with small connectivity: an exact solution