Solving the undirected feedback vertex set problem by local search
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\"odos-Renyi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Feedback Vertex Set (FVS)Similar Papers 제목 키워드 기반
Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT
We study practical approaches to solving the token swapping (TSWAP) problem optimally in this short paper. In TSWAP, we are given an undirected graph with colored vertices. A colored token is placed in each vertex. A pai…
Multi-Agent Path FindingEquivalence between LINE and Matrix Factorization
LINE [1], as an efficient network embedding method, has shown its effectiveness in dealing with large-scale undirected, directed, and/or weighted networks. Particularly, it proposes to preserve both the local structure (…
Network EmbeddingMulti-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering
We introduce multi-goal multi agent path finding (MAPF$^{MG}$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from the…
Heuristic SearchMulti-Agent Path FindingNavigateOn Structural Parameterizations of the Offensive Alliance Problem
The Offensive Alliance problem has been studied extensively during the last twenty years. A set $S\subseteq V$ of vertices is an offensive alliance in an undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as man…
Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback
The problem of online learning with graph feedback has been extensively studied in the literature due to its generality and potential to model various learning tasks. Existing works mainly study the adversarial and stoch…