English: NP-completeness reduction from an instance of vertex cover (yellow graph) to the feedback arc set problem (blue graph). This is the original reduction of Karp and Lawler published by Karp in 1972; it expands each yellow graph vertex into two adjacent blue graph vertices, and each undirected yellow graph edge into directed edges in opposite directions. The red edges show a minimum feedback arc set, corresponding to a minimum vertex cover consisting of the upper left and lower right yellow vertices.