Feedback Arc Set

Input

Directed graph $G = (V, A)$, positive integer $K \leq |A|$.

Question

Is there a subset $A' \subseteq A$ with $|A'| \leq K$ such that $A'$ contains at least one arc from every directed cycle in $G$?

Classes

• NP-complete

Comments

Remains NP-complete for digraphs in which no vertex has total in-degree and out-degree more than 3, and for edge digraphs (Gavril, 1977). Solvable in polynomial time for planar digraphs (Lucchesi, 1976). The corresponding problem for undirected graphs is trivially solvable in polynomial time.

Proofs

NP-complete

Transformation from Vertex Cover (Karp, 1972).

Reducible from

• Vertex Cover

References

• Gavril, F. (1977). “Some NP-complete problems on graphs”, Proc. 11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD.
• Lucchesi, C. L. (1976). A Minimax Equality for Directed Graphs. Thesis (Ph.D.)–University of Waterloo.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9