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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ You may find Menger's Theorem for digraphs useful. books.google.com/… $\endgroup$ – Austin Mohr Oct 12 '11 at 12:19
  • $\begingroup$ 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. $\endgroup$ – Dan W Oct 12 '11 at 20:37
  • 1
    $\begingroup$ An acyclic graph contains no cycles at all, rather than merely a vertex that's not in a cycle. $\endgroup$ – James Waldby - jwpat7 Oct 12 '11 at 21:26
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! I didn't expect an answer so long after asking the question $\endgroup$ – Szabolcs Nov 14 '11 at 19:40
  • 1
    $\begingroup$ @Szabolcs You are quite welcome. I guess thanks are due also to Community for poking old unanswered posts. =) $\endgroup$ – Srivatsan Nov 14 '11 at 19:44
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Oct 17 '11 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.