Spin glass phase transitions in the random feedback vertex set problem
arXiv:1603.09032 · doi:10.1103/PhysRevE.94.022146
Abstract
A feedback vertex set (FVS) of an undirected graph contains vertices from every cycle of this graph. Constructing a FVS of sufficiently small cardinality is very difficult in the worst cases, but for random graphs this problem can be efficiently solved after converting it into an appropriate spin glass model [H.-J. Zhou, Eur. Phys. J. B 86 (2013) 455]. In the present work we study the local stability and the phase transition properties of this spin glass model on random graphs. For both regular random graphs and Erdös-Rényi graphs we determine the inverse temperature at which the replica-symmetric mean field theory loses its local stability, the inverse temperature of the dynamical (clustering) phase transition, and the inverse temperature of the static (condensation) phase transition. We find that , , and change with the (mean) vertex degree in a non-monotonic way; is distinct from for regular random graphs of vertex degrees , while are always identical to for Erdös-Rényi graphs (at least up to mean vertex degree ). We also compute the minimum FVS size of regular random graphs through the zero-temperature first-step replica-symmetry-breaking mean field theory and reach good agreement with the results obtained on single graph instances by the belief propagation-guided decimation algorithm. Taking together, this paper presents a systematic theoretical study on the energy landscape property of a spin glass system with global cycle constraints.
arXiv comment15 pages, including 7 figures and 3 appendices. Submitted to PRE in February 2016
References in corpus (25)
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The structural glass transition and the entropy of the metastable states
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Statistical mechanics of the random K-SAT model
- Identifying optimal targets of network attack by belief propagation
- On the nature of the low-temperature phase in discontinuous mean-field spin glasses
- Reconstruction on trees and spin glass transition
- The number of matchings in random graphs
- Glass models on Bethe lattices
- Survey Propagation as local equilibrium equations
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- A ferromagnet with a glass transition
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Exact solutions for diluted spin glasses and optimization problems
- Spin glass approach to the feedback vertex set problem
- Optimizing spread dynamics on graphs by message passing
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- On independent sets in random graphs
- Minimal contagious sets in random regular graphs
- Potts Glass on Random Graphs
- The hard-core model on random graphs revisited
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- Solving the undirected feedback vertex set problem by local search
- mean-field population dynamics approach for the random 3-satisfiability problem