Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM FEEDBACK ARC SET

• INSTANCE: Directed graph $G=\left(V,A\right)$.
• SOLUTION: A feedback arc set, i.e., a subset $A'\subseteq A$ such that A' contains at least one arc from every directed cycle in G.
• MEASURE: Cardinality of the feedback arc set, i.e., $\vert A'\vert$.

  
  

• Good News: Approximable within $O(\log \vert V\vert \log\log \vert V\vert)$ [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 $O(\min(\log \vert V\vert\log\log \vert V\vert,\log^2 \vert S\vert))$ [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 $\vert E\vert^{\varepsilon }$ for some $\varepsilon >0$ [476]. The complementary problem of finding the maximum set of arcs A' such that $G'=\left(V,A'\right)$ is acyclic is approximable within ${2}/({1+\Omega(1/\sqrt{\Delta})})$ where $\Delta$ is the maximum degree [72] and [237], it is APX-complete [393], and if $\vert E\vert =\Theta(\vert V\vert^2)$ it admits a PTAS [36].
• Garey and Johnson: GT8