Spin glass phase transitions in the random feedback vertex set problem

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 ${\beta }_l$ at which the replica-symmetric mean field theory loses its local stability, the inverse temperature ${\beta }_d$ of the dynamical (clustering) phase transition, and the inverse temperature ${\beta }_c$ of the static (condensation) phase transition. We find that ${\beta }_l$, ${\beta }_d$, and ${\beta }_c$ change with the (mean) vertex degree in a non-monotonic way; ${\beta }_d$ is distinct from ${\beta }_c$ for regular random graphs of vertex degrees $K\ge 64$, while ${\beta }_d$ are always identical to ${\beta }_c$ for Erdös-Rényi graphs (at least up to mean vertex degree $c=512$). 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.

15 pages, including 7 figures and 3 appendices. Submitted to PRE in February 2016

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Potts Glass on Random Graphs
• Minimal contagious sets in random regular graphs
• Solving the undirected feedback vertex set problem by local search
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem

Cited by in corpus (3)

• Fast and simple decycling and dismantling of networks
• Spin-glass model for the C-dismantling problem
• K-core attack, equilibrium K-core, and kinetically constrained spin system