Spin Glass approach to the feedback vertex set problem
From MaRDI portal
(Redirected from 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
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A note on the cluster variation method.
- A Theory of Cooperative Phenomena
- 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
- scientific article; zbMATH DE number 5671622 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
(12)- Underestimated cost of targeted attacks on complex networks
- Optimal segmentation of directed graph and the minimum number of feedback arcs
- The characteristics of cycle-nodes-ratio and its application to network classification
- Minimal contagious sets in random regular graphs
- Circular convex bipartite graphs: feedback vertex sets
- A spin glass approach to the directed feedback vertex set problem
- Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
- Directed dominating set problem studied by cavity method: warning propagation and population dynamics
- Efficient network dismantling via node explosive percolation
- Hierarchical cycle-tree packing model for optimal K-core attack
- Minimum connected dominating set and backbone of a random graph
- Bounded degree nonnegative counting CSP
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)
