A greedy randomized adaptive search procedure for the Feedback Vertex Set Problem

A Greedy Randomized Adaptive Search Procedure (GRASP) is a randomized heuri stic that has produced high quality solutions for a wide range of combinato rial optimization problems. The NP-complete Feedback Vertex Set (FVS) Probl em is to find the minimum number of vertices that need to be removed from a directed graph so that the resulting graph has no directed cycle. The FVS problem has found applications in many fields, including VLSI design, progr am verification, and statistical inference. In this paper, we develop a GRA SP for the FVS problem. We describe GRASP construction mechanisms and local search, as well as some efficient problem reduction techniques. We report computational experience on a set of test problems using three variants of GRASP.