P. M. Pardalos, T. Qian, and M.G.C. Resende
J. of Combinatorial Optimization, vol. 2, pp. 399-412, 1999.
ABSTRACT
A Greedy Randomized Adaptive Search Procedure (GRASP)
is a randomized heuristic that has produced high quality solutions for a
wide range of combinatorial optimization problems. The NP-complete
Feedback Vertex Set (FVS) Problem 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, program
verification, and statistical inference. In this paper, we develop
a GRASP for the 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.