Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem

Abstract

In a spin glass system on a random graph, some vertices have their spins changing among different configurations of a ground--state domain. Long range frustrations may exist among these unfrozen vertices in the sense that certain combinations of spin values for these vertices may never appear in any configuration of this domain. We present a mean field theory to tackle such long range frustrations and apply it to the NP-hard minimum vertex cover (hard-core gas condensation) problem. Our analytical results on the ground-state energy density and on the fraction of frozen vertices are in good agreement with known numerical and mathematical results.

An erratum is added to the main text. 5 pages, 5 figures

References in corpus (6)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Coloring random graphs
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Statistical mechanics of the vertex-cover problem
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Properties of atypical graphs from negative complexities

Cited by in corpus (29)

• Critical phenomena in complex networks
• On the dynamics of the glass transition on Bethe lattices
• Inducing Effect on the Percolation Transition in Complex Networks
• Message passing for vertex covers
• Statistical Mechanics of the Minimum Dominating Set Problem
• Statistical Mechanics of maximal independent sets
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Fluctuation of Dynamical Robustness in a Networked Oscillators System
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Phase transition for cutting-plane approach to vertex-cover problem
• Higher order corrections to the effective potential close to the jamming transition in the perceptron model
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Two faces of greedy leaf removal procedure on graphs
• Optimal Location of Sources in Transportation Networks
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Statistical Physics of Group Testing
• Self-sustained Clusters and Ergodicity Breaking in Spin Models
• The network source location problem: ground state energy, entropy and effects of freezing
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking