1307.6948 (Hai-Jun Zhou)
Hai-Jun Zhou
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 certain given value. This combinatorial optimization problem has many practical applications, but it can be extremely difficult to solve as it belongs to the nondeterministic polynomial-complete (NP-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. A key novelty of our model is that the global cycle constraints are represented through the local constraints on all the edges of the graph. After this mapping from the global cycle constraints to the local edge constraints, the FVS problem can then be treated by distributed message-passing procedures such as belief propagation. We demonstrate that the belief propagation-guided decimation algorithm based on our spin glass model is able to construct nearly optimal feedback vertex sets for single random graph instances. We also construct a spin glass model for the FVS problem on a directed graph. Our theoretical work may also shed light on designing suitable spin glass models for hard optimization problems with other global constraints.
View original:
http://arxiv.org/abs/1307.6948
No comments:
Post a Comment