Spin Glass approach to the feedback vertex set problem
From MaRDI portal
Publication:6176705
DOI10.1140/EPJB/E2013-40690-1zbMATH Open1515.82158arXiv1307.6948OpenAlexW2010280523MaRDI QIDQ6176705FDOQ6176705
Authors: Haijun Zhou 
Publication date: 26 July 2023
Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1307.6948
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
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- The complexity of theorem-proving procedures
- On Ising's model of ferromagnetism
- Decycling graphs
- Decycling numbers of random regular graphs
- Information, Physics, and Computation
- Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
- Statistical theory of superlattices
- A Theory of Cooperative Phenomena
- Dynamics and control at feedback vertex sets. II: A faithful monitor to determine the diversity of molecular activities in regulatory networks
- Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks
- A note on the cluster variation method.
- Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
- Observability of complex systems
- Algorithm for counting large directed loops
- Loops of any size and Hamilton cycles in random scale-free networks
- Title not available (Why is that?)
- Statistical theory of superlattices with unequal concentrations of the components
- On the number of circuits in random graphs
Cited In (11)
- 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
- Directed dominating set problem studied by cavity method: warning propagation and population dynamics
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)
