1

We have to find out the minimum number of edges to be deleted in a directed graph to just remove the all cycles.enter image description here

For example:- in this graph, there are 3 cycles:

1) 0-1-2-0

2) 0-2-0

3) 3-3

There are two possible combinations to remove all the cycles:

1) Delete edges 2-0 and 3-3.

2) Delete edges 0-2, 1-2 and 3-3.

In first case we have to delete 2 edges and in second case, we have to delete 3 edges.

First combination is the solution.

Satender
  • 117
  • 1
  • 2
  • 9

1 Answers1

4

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.

Kaidul
  • 15,409
  • 15
  • 81
  • 150
  • Thanks dear, i didn't knew the problem exists. I was just wondering a different question and i by chance discovered this one. – Satender May 30 '17 at 07:03
  • @Satender : ​ However, this paper shows that small feedback sets can be found fairly-efficiently. ​ ​ ​ ​ –  May 31 '17 at 05:09