Applying local search to the feedback vertex set problem

作者：Galinier Philippe^*; Lemamou Eunice; Bouzidi Mohamed Wassim

来源：Journal of Heuristics, 2013, 19(5): 797-818.

DOI：10.1007/s10732-013-9224-z

The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In spite of the importance of this NP-hard problem, no local search approach had been proposed so far for tackling it. Building on a property of acyclic graphs, we suggest in this paper a new representation of the solutions of the FVSP (feedback sets). Thanks to this solution representation, we are able to design a local transformation (equivalent to a neighborhood) that changes a feedback set into a new one. Based on this neighborhood, we have developed a simulated annealing algorithm for the FVSP. Our experiments show that our algorithm outperforms the best existing heuristic, namely the greedy adaptive search procedure by Pardalos et al.

• 出版日期2013-10