algorithm to test whether G contains an arborescence

Question

An arborescence of a directed graph G is a rooted tree such that there is a directed path from the root to every other vertex in the graph. Give an efficient and correct algorithm to test whether G contains an arborescence, and its time complexity.

I could only think of running DFS/BFS from every node till in one of the DFS all the nodes are covered. I thought of using min spanning tree algorithm, but that is also only for un-directed graphs

is there any other efficient algorithm for this ?

I found a follow up question which state there is a O(n+m) algorithm for the same, can anybody help what could be the solution ?

Answer 1

What you are exactly looking for is the so called Edmond's algorithm. The minimum spanning tree algorithms are not going to work on directed graphs but that is the idea. The MST problem became arborescence problem when the graph is directed and arborescence is what you have described above.

The naive complexity is O(EV) just like the Prim's algorithm for undirected MST problem but I am sure there are faster implementations of it.

For more information you can check the wiki page:

Edmonds Algorithm

Answer 2

First note that the definition for an arborescence of a directed graph given in the question above is a bit different from the one given in e.g. Wikipedia: your question's definition does not require that the path be unique, nor does it require that the original directed graph G be a weighted one. So a solution should be simpler than the one handled by Edmond's Algorithm.

How about the following: first part will be to find an adequate root. Once an adequate root is found, running a simple DFS on the graph G starting from that root should allow us to create the needed tree and we're done. So how can we find such a root?

• Start by running DFS and "reduce" any cycle found to a single edge. Inside any cycle found, it won't matter which edge we use as any of them can reach any other. If a single edge is left after this reduction it means the entire graph is strongly connected and so any edge - including the only one left - can fit as root.

• If more than one edge is left, go over all remaining edges, and find the ones having an in-degree of zero. If more than one is found - then we can't construct the needed tree - as they can't be reached from one another. If just a single edge is found here - that's our root edge.

Complexity is O(edges + vertices) in say an adjacency list representation of the graph.