is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition):

A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Previous threads on this question are here and here. In that second thread, one of the answers links to a preprint by someone who corresponded with one of the authors of the book, and stated (in the abstract of the preprint) that the solution the authors intended was (if I'm understanding correctly) to call DFS-VISIT(G, u) (from p. 604 of CLRS) on each vertex $u$ of the graph, resetting all vertex colors back to white (to indicate unvisited) in between calls, and return false (for "not singly connected") whenever a forward edge or cross edge is found, and returning true otherwise. This would take O(VE) time.

There seems to be some confusion in the answers and comments section of those threads: the above scheme is referred to as "calling DFS on every vertex". In fact, this is different from the DFS algorithm presented on p. 604 of CLRS, which calls DFS-VISIT on all unvisited nodes in the graph, without resetting the colors in between calls, which takes $O(V + E)$ time.

My question is, instead of doing what is stated in the preprint, which takes O(VE) time, is it sufficient to simply perform the ordinary $O(V + E)$ DFS on the graph, and return false (for "not singly connected") whenever a forward edge or a cross edge that is located entirely within a single DF tree is found? (As correctly pointed out in one of the comments in the second thread linked above, a cross edge within a single DF tree means the graph is certainly not singly connected, but a cross edge between two vertices in different trees does not necessarily mean so).

In other words, is it possible to have a non-singly connected graph, such that for some ordering of the adjacency lists, performing the DFS algorithm from p. 604 of CLRS will not find any forward edges or cross edges within individual trees, but possibly only cross edges between trees, if any?

• It is an open problem whether singly-connectedness can be determined in $O(|V|+|E|)$ time. Jan 24 '19 at 19:55

2 Answers

I just realized, a single call to DFS is not sufficient, since the conjecture I asked about is not true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $$u$$, and $$v$$ is a descendant of $$u$$. Then suppose an unvisited vertex $$w$$ has both $$u$$ and $$v$$ in its adjacency list. Then, $$w$$ would not be in the same tree as $$u$$ and $$v$$, but there would be cross-tree edges $$(w, u)$$ and $$(w, v)$$, and hence there would be more than two paths from $$w$$ to $$v$$, making the graph not singly connected.

However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $$(w,u)$$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $$(w,v)$$ cross edge.

You can check if there is already a path between u and v, using their finishing and discovery time (d[u] u is an ancestor of v). If their times are disjoint, then they are on different branches and not reachable from one another, so there shouldn't be more than one path between w and u or w and v.

• Can you explain why must nodes that are on different branches from the DFS call from a single source are not reachable from eachother? I am not sure what you mean by branches, but I don't think that this is true in general if branches refers to the tree is created by the single source DFS call. Jan 23 '19 at 15:55
• Well, if they were reachable from one another, than that would be a cross edge, and that isn't good. Suppose you have a cross edge between u and v. Than you could reach v in two ways: directly from the source or through u. So that would instantly tell that the graph is not good. If the cross edge is between two trees, than you could put it aside and check it later the way I described above? Jan 23 '19 at 16:29
• pretty sure this answer is wrong since it only handles the case of $(w, u)$ and $(w,v)$. For other cases like $(w,u)$ and $(x,v)$ you would still be able to tell from the disjointness of the eight times whether there's an alternate path, but it's unclear how to find all such cross edge pairs to test. As far as I know, the simple $O(V^2)$ method is still required. Dec 23 '20 at 23:36