05946685

a

05946685 Carrabs, Francesco Cerulli, Raffaele Gentili, Monica Parlato, Gennaro A tabu search heuristic based on $k$-diamonds for the weighted feedback vertex set problem. Pahl, Julia (ed.) et al., Network optimization. 5th international conference, INOC 2011, Hamburg, Germany, June 13--16, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21526-1/pbk). Lecture Notes in Computer Science 6701, 589-602 (2011). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-21527-8_66

Summary: Given an undirected and vertex weighted graph $G = (V,E,w)$, the Weighted Feedback Vertex Problem (WFVP) consists of finding a subset $F \subseteq V$ of vertices of minimum weight such that each cycle in $G$ contains at least one vertex in $F$. The WFVP on general graphs is known to be NP-hard and to be polynomially solvable on some special classes of graphs (e.g., interval graphs, co-comparability graphs, diamond graphs). In this paper we introduce an extension of diamond graphs, namely the $k$-diamond graphs, and give a dynamic programming algorithm to solve WFVP in linear time on this class of graphs. Other than solving an open question, this algorithm allows an efficient exploration of a neighborhood structure that can be defined by using such a class of graphs. We used this neighborhood structure inside our Iterated Tabu Search heuristic. Our extensive experimental results show the effectiveness of this heuristic in improving the solution provided by a 2-approximate algorithm for the WFVP on general graphs.