2

Given a directed graph, remove the edge between two nodes if there is an alternate path between them. Ex: given a->b, b->c, a->c, remove a->c. Is there an efficient algorithm to count the number of those removed edges?

Seraph
  • 177
  • 12
  • 3
    Have you seen [this related post](https://stackoverflow.com/questions/510277/algorithm-for-finding-redundant-edges-in-a-graph-or-tree)? – Axel Kemper Jun 02 '18 at 16:35
  • @AxelKemper I didn't find that post, thank you so much – Seraph Jun 02 '18 at 17:59
  • Possible duplicate of [Algorithm for Finding Redundant Edges in a Graph or Tree](https://stackoverflow.com/questions/510277/algorithm-for-finding-redundant-edges-in-a-graph-or-tree) – Yola Jun 02 '18 at 19:34

1 Answers1

0

From wiki Strongly connected component:

A directed graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every nontrivial strongly connected component contains at least one directed cycle.

You can use Tarjan's strongly connected components algorithm to find SCC. And then delete one edge from every component.

Next you need iterate the whole process as every nontrivial strongly connected component contains at least one directed cycle.

In general counting number of cycles is NP-hard as if you can count all cycles in polynomial time then you can detect the existence of Hamiltonian cycle as well. But Hamiltonian path is NP-hard.

Yola
  • 18,496
  • 11
  • 65
  • 106