Speaker
Prof.
Hai-Jun Zhou
(Institute of Theoretical Physics, the Chinese Academy of Sciences)
Description
A feedback vertex set (FVS) of an undirected or directed graph is a set of vertices that contains at least one vertex of each (directed) 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 is one of the basic global-constraint optimization problems, and it has many practical applications. But this problem is in the non-deterministic polynomial-complete class of worst-case computational complexity, and therefore could be extremely difficult to solve.
In this presentation I introduce 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 find the solution space of random FVS problem has very rich structures. The system may have two spin glass transitions: a dynamical spin glass transition (the clustering transition) and a separated static spin glass transition (the condensation transition).
Author
Prof.
Hai-Jun Zhou
(Institute of Theoretical Physics, the Chinese Academy of Sciences)
