The feedback arc set problem asks, for a directed graph 
and a positive integer 
, whether there is a set 
of at most 
directed edges whose removal
makes 
an acyclic digraph. Equivalently, 
must contain at least one graph
edge of every directed graph cycle in 
.
The decision problem is NP-complete (Karp 1972). The corresponding optimization problem asks for a feedback arc set of minimum cardinality.
