The feedback vertex set (FVS) problem can be stated as follows: Given a directed graph G(V,E), where V denotes the set of n vertices and E the set of arcs, find a minimum cardinality subset V' of V such that every directed cycle in G contains at least one vertex in V'. In other words, we wish to determine how to remove the minimum number of vertices from the original graph such that the resulting graph has no directed cycle.
In this talk, we present a survey of recent heuristics for
the FVS, including a Greedy Randomized Adaptive Search Procedure
(GRASP) which can be easily parallelized.
Back to Workshop Schedule