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?

Packhorse

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.

Underground

I've read elsewhere that running DFS once on the whole tree should suffice. Is it necessary to run on each vertex? – Packhorse

It suffices to repeat for every unvisited vertex, but you have to re-traverse everything downstream (even those marked "unvisited"). So you'd need both "ever visited" and "visited this time" marks. – Sinapism

shouldn't running DFS once be enough, after we run DFS, we check that there are no cross-edges and forward-edges and we are done? Is there a case where running one DFS with checking cross-edges and forward-edges not enough since any more than one path between any two nodes u and v will show in our DFS? – Hypoblast

Cross edges are not a violation of a singly-connected graph if they are between trees in a DFS forest. The cross-edge may be on the only path from u to v. – Gujranwala

in that case, is it enough to run DFS once, and check if there are any forward edges or intra-tree cross edges? That would be O(V + E)... – Corene

i just wanted to clarify, many of the answers here talk about doing DFS on every vertex, while some comments have pointed out that inter-tree cross edges do not necessarily mean the graph is not singly connected. I think these are dealing with two completely different situations; the O(|V| |E|) algorithm described in the document linked in HsnVahedi's answer is actually calls DFS-VISIT on every node, and resetting between calls, not DFS, hence there would be no inter-tree edges, since we only deal with one tree at a time. – Corene

@CarlG , I just realized, by "run DFS on every vertex", what is actually meant is "run DFS-VISIT on every vertex, resetting all colors back to white (unvisited) in between calls". This way, there cannot be any cross-tree cross edges. Also, the my conjecture that it may be possible to check for single-connectedness using a single call to DFS is false, as seen in another thread I just created) – Corene

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).

Ushijima

What if the cross edge is from a root of a different tree to one of the children of another tree. This is a completely legitimate edge. – Discontinuity

Why are backedges relevant? Aren't they never walked on a simple path? – Ivey

@pkoch, he already said that in 3) if there are two backedges in tree rooted at vertex u, to proper ancestors of u, then it is not singly connected, cuz a directed ring with one back edge is still a singly connected graph – Po

The third point can be simply done using an array for the count of number of back edges from a certain vertex. Whenever the back edge is directed to a proper ancestor in the SCC, we increment the arr[v] by 1. When it reaches >=2 we break it. This question is much similar to finding unique path graph in time linear order of vertices. One must use SCC to solve such questions. A lot of checks can be made simple using SCCs and SCC graph. – Shae

Answer 3

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).

Stentorian

Answer 4

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.

Pugh

Answer 5

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

Gloaming

Answer 6

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)

Adeliaadelice