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

Question

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?

Answer 1

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. ]

The above decision version of this problem is NP-complete. In fact, it is one of Richard Karp's 21 NP-completeness problems. That is, unless NP collapses to P--widely believed to be unlikely--this problem will not admit a polynomial time algorithm. You can look up the details from the wikipedia page.

Answer 2

You can start off by finding all cycles in the graph. You can be sure that, for each cycle, at least one of the edges (links) in it are going to be removed. You save for each edge, how many cycles it is contained in. Then, start removing edges greedily until all cycles are gone. This isn't very efficient, though.

Answer 3

As answered above, the problem is NP-complete. The wikipedia page doesn't state the algorithm explicitly though. The most elegant method I found is a simple $2^n$ sized dynamic program. It goes as:
Let $S$ denote an arbitrary subset of nodes, $f(S)$ be the number of arcs in the minimum arc set for the subgraph consisting of the nodes in $S$.
Let $c(k,S')$ denote the number of arcs from node $k$ to nodes in the subset $S'$.
Then (assuming no self loops): $$f(S)=\min_{\forall S'\subset S\\ k \in K \text{ s.t.}S=S'\cup K}\{f(S')+c(k,S') \}$$ Naturally, the base case will be:
For $S'$ unary $f(S')=0, c(k,S')=1$. Naturally this is an $\mathcal{O}(n\times 2^n)$ algorithm, with memory complexity of $\mathcal{O}(2^n)$.