.
such that
A'
contains at least one arc from every directed cycle in
G
.
[
99
].
[
99
].
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
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
[
352
].
The complementary problem of finding the maximum set of arcs
A'
such that
is acyclic is approximable within
where
is the maximum degree
[
44
] and [
161
], it is A
PX
-complete
[
284
],
and if
it admits a PTAS [
23
].
Viggo Kann