** Next:** MINIMUM MAXIMAL MATCHING
** Up:** Covering and Partitioning
** Previous:** MINIMUM FEEDBACK VERTEX SET
** Index**

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

*Good News:*
Approximable within
[148].
*Bad News:*
APX-hard [282].
*Comment:*
Transformation from MINIMUM FEEDBACK VERTEX SET [148].
The generalized variation in which the input is extended with a *subset* *S*
of vertices and arcs, and the problem is to find an arc set that
contains at least one arc from every directed cycle that intersects *S*,
is approximable within
[148].
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 *A*, and the problem is to find the feedback
arc set of size *k* that contains the largest number of arcs from *S*,
is not approximable within
for some
[476].
The complementary problem of finding the maximum set of arcs *A'* such that
is acyclic is approximable within
where
is the maximum degree
[72] and [237], it is APX-complete
[393],
and if
it admits a PTAS [36].
*Garey and Johnson:* GT8

** Next:** MINIMUM MAXIMAL MATCHING
** Up:** Covering and Partitioning
** Previous:** MINIMUM FEEDBACK VERTEX SET
** Index**
*Viggo Kann*

*2000-03-20*