5
$\begingroup$

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?

  • 1
    An acyclic graph contains no cycles at all, rather than merely a vertex that's not in a cycle.2011-10-12

2 Answers 2

6

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.

  • 1
    @Szabolcs You are quite welcome. I guess thanks are due also to [Community](http://math.stackexchange.com/users/-1/community) for poking old unanswered posts. =)2011-11-14
0

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.

  • 0
    Can you prove that this will give the *minimum* number of edges to be removed? Also, can you suggest a way to find all cycles? I think the total number of cycles will grow extremely fast with the vertex count in a sufficiently dense graph.2011-10-17