Ground-State Entropy of the Random Vertex-Cover Problem

Abstract

Counting the number of ground states for a spin-glass or NP-complete combinatorial optimization problem is even more difficult than the already hard task of finding a single ground state. In this paper the entropy of minimum vertex-covers of random graphs is estimated through a set of iterative equations based on the cavity method of statistical mechanics. During the iteration both the cavity entropy contributions and cavity magnetizations for each vertex are updated. This approach overcomes the difficulty of iterative divergence encountered in the zero temperature first-step replica-symmetry-breaking (1RSB) spin-glass theory. It is still applicable when the 1RSB mean-field theory is no longer stable. The method can be extended to compute the entropies of ground-states and metastable minimal-energy states for other random-graph spin-glass systems.

4 pages, 2 figures. Final version as appear in PRE

References in corpus (12)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• The number of matchings in random graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Landscape of solutions in constraint satisfaction problems
• Message passing for vertex covers
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Statistical mechanics of the vertex-cover problem
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses

Cited by in corpus (9)

• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• A theory of non-equilibrium local search on random satisfaction problems
• Two faces of greedy leaf removal procedure on graphs
• Cavity approach to the Sourlas code system
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• The network source location problem: ground state energy, entropy and effects of freezing
• Organization mechanism and counting algorithm on Vertex-Cover solutions