GT8 M INIMUM F EEDBACK V ERTEX S ET

     
• I NSTANCE : Directed graph .
• S OLUTION : A feedback vertex set, i.e., a subset such that V' contains at least one vertex from every directed cycle in G .
• M EASURE : Cardinality of the feedback vertex set, i.e., |V'| .

• Good News: Approximable within [ 317 ] and [ 99 ].
• Bad News: A PX -hard [ 200 ].
• Comment: Transformations from M INIMUM V ERTEX C OVER and M INIMUM F EEDBACK A RC S ET [ 27 ]. On undirected graphs the problem is A PX -complete and approximable within 2, even if the vertices are weighted [ 30 ]. 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 [ 99 ] and within 8 on undirected graphs [ 100 ]. All these problems are approximable within 9/4 for planar graphs [ 136 ].     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 [ 352 ].
• Garey and Johnson: GT7