- INSTANCE: Directed graph .
- SOLUTION:
A feedback vertex set, i.e., a subset
such that
*V'*contains at least one vertex from every directed cycle in*G*. - MEASURE:
Cardinality of the feedback vertex set, i.e., .

*Good News:*Approximable within [435] and [148].*Bad News:*APX-hard [282].*Comment:*Transformations from MINIMUM VERTEX COVER and MINIMUM FEEDBACK ARC SET [46]. On undirected graphs the problem is APX-complete and approximable within 2, even if the vertices are weighted [50]. The generalized variation in which the input is extended with a subset*S*of vertices and arcs, and the problem is to find a vertex set that contains at least one vertex from every directed cycle that intersects*S*, is approximable within on directed graphs [148] and within 8 on undirected graphs [149]. All these problems are approximable within 9/4 for planar graphs [199]. The constrained variation in which the input is extended with a positive integer*k*and a subset*S*of*V*, and the problem is to find the feedback vertex set of size*k*that contains the largest number of vertices from*S*, is not approximable within for some [476].*Garey and Johnson:*GT7