Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem

Abstract

The vertex-cover problem is a prototypical hard combinatorial optimization problem. It was studied in recent years by physicists using the cavity method of statistical mechanics. In this paper, the stability of the finite-temperature replica-symmetric (RS) and the first-step replica-symmetry-broken (1RSB) cavity solutions of the vertex cover problem on random regular graphs of finite vertex-degree $K$ are analyzed by population dynamics simulations. We found that (1) the lowest temperature for the RS solution to be stable, $T_{RS}(K)$, is not a monotonic function of $K$, and (2) at relatively large connectivity $K$ and temperature $T$ slightly below the dynamic transition temperature $T_d(K)$, the 1RSB solutions with small but non-negative complexity values are stable. Similar results are obtained on random Poissonian graphs.

15 pages, 9 figures

References in corpus (16)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Loop series for discrete statistical models on graphs
• Reconstruction on trees and spin glass transition
• The number of matchings in random graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Immunization of Real Complex Communication Networks
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Message passing for vertex covers
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Potts Glass on Random Graphs
• Near optimal configurations in mean field disordered systems
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses

Cited by in corpus (17)

• Avalanches in mean-field models and the Barkhausen noise in spin-glasses
• Tropical Tensor Network for Ground States of Spin Glasses
• The hard-core model on random graphs revisited
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Solution space structure of random constraint satisfaction problems with growing domains
• Cavity approach to the Sourlas code system
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Two faces of greedy leaf removal procedure on graphs
• Spin glass phase transitions in the random feedback vertex set problem
• Spin-glass model for the C-dismantling problem
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• Typical Performance of Approximation Algorithms for NP-hard Problems
• The network source location problem: ground state energy, entropy and effects of freezing
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Statistical mechanics of the minimum vertex cover problem in stochastic block models