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].