  A feedback vertex set (FVS) of an undirected graph is a set of vertices that
contains at least one vertex of each cycle of the graph. The feedback vertex
set problem consists of constructing a FVS of size less than a certain given
value. This combinatorial optimization problem has many practical applications,
but it is in the nondeterministic polynomial-complete class of worst-case
computational complexity. In this paper we define a spin glass model for the
FVS problem and then study this model on the ensemble of finite-connectivity
random graphs. In our model the global cycle constraints are represented
through the local constraints on all the edges of the graph, and they are then
treated by distributed message-passing procedures such as belief propagation.
Our belief propagation-guided decimation algorithm can construct nearly optimal
feedback vertex sets for single random graph instances and regular lattices. We
also design a spin glass model for the FVS problem on a directed graph. Our
work will be very useful for identifying the set of vertices that contribute
most significantly to the dynamical complexity of a large networked system.
