title: Spin-glass phase transitions and minimum energy of 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 by converting it into an appropriate spin-glass model [H.-J. Zhou, Eur. Phys. J. B 86, 455 (2013)EPJBFY1434-602810.1140/epjb/e2013-40690-1]. In the present work we study the spin-glass phase transitions and the minimum energy density of the random FVS problem by the first-step replica-symmetry-breaking (1RSB) mean-field theory. For both regular random graphs and Erdös-Rényi graphs, we determine the inverse temperature β_{l} at which the replica-symmetric mean-field theory loses its local stability, the inverse temperature β_{d} of the dynamical (clustering) phase transition, and the inverse temperature β_{s} of the static (condensation) phase transition. These critical inverse temperatures all change with the mean vertex degree in a nonmonotonic way, and β_{d} is distinct from β_{s} for regular random graphs of vertex degrees K>60, while β_{d} are identical to β_{s} for Erdös-Rényi graphs at least up to mean vertex degree c=512. We then derive the zero-temperature limit of the 1RSB theory and use it to compute the minimum FVS cardinality.
authors.affiliation: Institute of Theoretical Physics, Chinese Academy of Sciences, Zhong-Guan-Cun East Road 55, Beijing 100190, China.|College of Science, Civil Aviation University of China, Tianjin 300300, China.
authors.forename: Shao-Meng
authors.initials: SM
authors.lastname: Qin
authors.affiliation: Beijing National Laboratory for Condensed Matter Physics and Key Laboratory of Soft Matter Physics, Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China.
authors.forename: Ying
authors.initials: Y
authors.lastname: Zeng
authors.affiliation: Institute of Theoretical Physics, Chinese Academy of Sciences, Zhong-Guan-Cun East Road 55, Beijing 100190, China.|School of Physical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China.
authors.forename: Hai-Jun
authors.initials: HJ
authors.lastname: Zhou