Next: MINIMUM FEEDBACK ARC SET
Up: Covering and Partitioning
Previous: MINIMUM EDGE COLORING
  Index
- 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
Viggo Kann
1999-04-22