Spin Glass approach to the feedback vertex set problem
From MaRDI portal
Publication:6176705
Abstract: 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.
Recommendations
- A spin glass approach to the directed feedback vertex set problem
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Two Hardness Results on Feedback Vertex Sets
- Exact localisations of feedback sets
- scientific article; zbMATH DE number 1003266
Cites work
- scientific article; zbMATH DE number 5671622 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A Theory of Cooperative Phenomena
- A note on the cluster variation method.
- Algorithm for counting large directed loops
- Decycling graphs
- Decycling numbers of random regular graphs
- Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks
- Dynamics and control at feedback vertex sets. II: A faithful monitor to determine the diversity of molecular activities in regulatory networks
- Information, Physics, and Computation
- Loops of any size and Hamilton cycles in random scale-free networks
- Observability of complex systems
- On Ising's model of ferromagnetism
- On the number of circuits in random graphs
- Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
- Reducibility among combinatorial problems
- Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
- Statistical theory of superlattices
- Statistical theory of superlattices with unequal concentrations of the components
- The complexity of theorem-proving procedures
Cited in
(11)- Directed dominating set problem studied by cavity method: warning propagation and population dynamics
- A spin glass approach to the directed feedback vertex set problem
- Efficient network dismantling via node explosive percolation
- Hierarchical cycle-tree packing model for optimal \(K\)-core attack
- Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
- Circular convex bipartite graphs: feedback vertex sets
- The characteristics of cycle-nodes-ratio and its application to network classification
- Underestimated cost of targeted attacks on complex networks
- Minimum connected dominating set and backbone of a random graph
- Optimal segmentation of directed graph and the minimum number of feedback arcs
- Minimal contagious sets in random regular graphs
This page was built for publication: Spin Glass approach to the feedback vertex set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176705)
