Next: MINIMUM FEEDBACK ARC SET Up: Covering and Partitioning Previous: MINIMUM EDGE COLORING Index

### MINIMUM FEEDBACK VERTEX SET

- 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., |V'|.

- Good News: Approximable within [412] and [137].

- Bad News: APX-hard [267].

- Comment: Transformations from MINIMUM VERTEX COVER and MINIMUM FEEDBACK ARC SET [43]. On undirected graphs the problem is APX-complete and approximable within 2, even if the vertices are weighted [47]. 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 [137] and within 8 on undirected graphs [138]. All these problems are approximable within 9/4 for planar graphs [187]. 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 [452].

- Garey and Johnson: GT7

Next: MINIMUM FEEDBACK ARC SET Up: Covering and Partitioning Previous: MINIMUM EDGE COLORING Index