Spin glass phase transitions in the random feedback vertex set problem

Shao-Meng Qin, Ying Zeng, Hai-Jun Zhou

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 w…