Solving the undirected feedback vertex set problem by local search

Abstract

An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, then a feedback vertex set (FVS) is a set of vertices intersecting with each of these cycles. Constructing a FVS of cardinality approaching the global minimum value is a optimization problem in the nondeterministic polynomial-complete complexity class, therefore it might be extremely difficult for some large graph instances. In this paper we develop a simulated annealing local search algorithm for the undirected FVS problem. By defining an order for the vertices outside the FVS, we replace the global cycle constraints by a set of local vertex constraints on this order. Under these local constraints the cardinality of the focal FVS is then gradually reduced by the simulated annealing dynamical process. We test this heuristic algorithm on large instances of Erödos-Renyi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.

6 pages

References in corpus (8)

• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Spin glass approach to the feedback vertex set problem
• From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
• Statistical Mechanics of Steiner trees
• Networking - A Statistical Physics Perspective
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
• Activity patterns on random scale-free networks: Global dynamics arising from local majority rules

Cited by in corpus (8)

• Vital nodes identification in complex networks
• Identifying optimal targets of network attack by belief propagation
• Minimal contagious sets in random regular graphs
• Spin glass phase transitions in the random feedback vertex set problem
• Spin-glass model for the C-dismantling problem
• Feedback arcs and node hierarchy in directed networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs