Vertex cover problem studied by cavity method: Analytics and population dynamics

Abstract

We study the vertex cover problem on finite connectivity random graphs by zero-temperature cavity method. The minimum vertex cover corresponds to the ground state(s) of a proposed Ising spin model. When the connectivity c>e=2.718282, there is no state for this system as the reweighting parameter y, which takes a similar role as the inverse temperature βin conventional statistical physics, approaches infinity; consequently the ground state energy is obtained at a finite value of y when the free energy function attains its maximum value. The minimum vertex cover size at given c is estimated using population dynamics and compared with known rigorous bounds and numerical results. The backbone size is also calculated.

7 pages (including 3 figures and 1 table), REVTeX4 format

Cited by in corpus (25)

• Critical phenomena in complex networks
• Core percolation on complex networks
• Message passing for vertex covers
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Statistical Mechanics of maximal independent sets
• 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
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• 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
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Properties of atypical graphs from negative complexities
• Solution-space structure of (some) optimization problems
• Two faces of greedy leaf removal procedure on graphs
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Spin glass phase transitions in the random feedback vertex set problem
• Statistical Physics of Group Testing
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem