# Find the minimum number of links to remove from digraph to make it acyclic

As the title says, I am looking for a way to find the minimum number of links to remove from a directed graph to make it acyclic. I am looking both for the minimum number, as well as an actual set of links to remove.

How can this be done in a reasonably simple and efficient way?

EDIT: In other words, how can I label/order the vertices of the graph so that the adjacency matrix will contain most (nonzero) elements below the diagonal?

• You may find Menger's Theorem for digraphs useful. books.google.com/… – Austin Mohr Oct 12 '11 at 12:19
• Would it work to just find the vertex with the least number of incoming edges and remove those? Then you have a vertex that can never be reached, hence acyclic. – Dan W Oct 12 '11 at 20:37
• An acyclic graph contains no cycles at all, rather than merely a vertex that's not in a cycle. – James Waldby - jwpat7 Oct 12 '11 at 21:26

This problem is well-known under the name minimum feedback arc set problem. The decision version of the problem says: given a graph $G$ and a parameter $k$, can we break all cycles in $G$ by deleting some set of at most $k$ arcs from it? [Note that, as usual, the decision version is no harder than the computational one of finding the minimum feedback arc set. ]