Input: directed graph G = (V, E), a positive integer k

PROB: is it possible to obtain a directed acyclic graph by removing at most k edges from E

Prove that PROB is np-complete.

Steps: reduction from vertex cover (VC)...

From the input (G=(V, E), k) for VC, construct a new directed graph G'=(V',E') with 2n vertices and n+2m edges.

V?={v1,,vn,v?1,,v?n} and E?={(vi,v?i) : i?n} ? {(v?i,vj), (v?j,vi) : (vi,vj) ? E}...