What is the most efficient way to determine if a directed graph is singly connected?

Question

I am working on an assignment where one of the problems asks to derive an algorithm to check if a directed graph G=(V,E) is singly connected (there is at most one simple path from u to v for all distinct vertices u,v of V.

Of course you can brute force check it, which is what I'm doing right now, but I want to know if there's a more efficient way. Could anyone point me in the right direction?

Answer 1

Have you tried DFS.

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

Complexity O(v^2), o(v) dfs as no repetition.

Answer 2

There is a better answer for this question. you can do that in O(|V|^2). and with more effort you can do it in linear time.

First you find strongly connected components of G. in each strong component, you search to find this cases: 1) if there is a forward edge in this component, it is not singly connected, 2) if there is a cross edge in this component, it is not singly connected, 3) if there are at least two back edges in tree rooted at vertex u, to proper ancestors of u, then it is not singly connected.

this can be done in O(E). ( I think except for case 3. I couldn't implement it well!! ).

If none of cases above occurred, you should check whether there is a cross edge or a forward edge on G^SCC ( graph G, with strong components replaced with single nodes), since we don't have backedges, it can be done by repeating dfs on each vertex of this graph in O(|V|^2).

Answer 3

Read this one. It really explains well.

Answer 4

I don't agree that its complexity will be O(V^2), as In DFS we don't call it for every vertex as see in Introduction to algorithm book also, syntax is DFS(G). We only call DFS for whole graph not for any single vertex unlike BFS. So here in this case according to me we have to check it by calling DFS once.If a visited vertex is encountered again, the graph is not singly connected(definitely we have to call it for every disconnected component but it already included in the code). SO the complexity will be O(V+E). As here E=V therefore complexity should be O(V).

Answer 5

I thought of this : 1) Run DFS from any vertex, if all vertices are covered in the DFS with no forward edges(there can be no cross as else not all vertices will be covered), then it can be a potential candidate.

2) If a vertex(level j) which is found in the DFS has a back edge to level i then no other vertex found after it should have a back edge toward any vertex with level less than j and every vertex much be reachable to the root(checked with second DFS).

This does it in linear time if this is correct.

Answer 6

Take a look at the definition of simple path. A cyclic graph can be singly connected. DFS won't work for A->B, B->A, which is singly connected.

The following paper uses strongly connected component to solve this.

https://www.cs.umd.edu/~samir/grant/khuller99.ps

Answer 7

Run DFS once from each vertex. The graph is singly connected if and only if there are no forward edges and there are no cross edges within a component.

Complexity : O(V.E)