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

### MINIMUM FEEDBACK ARC SET

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

- Good News: Approximable within [137].

- Bad News: APX-hard [267].

- Comment: Transformation from MINIMUM FEEDBACK VERTEX SET [137]. 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 [137]. 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 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 [452]. The complementary problem of finding the maximum set of arcs A' such that is acyclic is approximable within where is the maximum degree [67] and [220], it is APX-complete [371], and if it admits a PTAS [34].
- Garey and Johnson: GT8

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