In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem: 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. I took this to mean the following: for each $u, v \in V$ , there is at most one simple path from $u$ to $v$ in $G$ . According to this preprint, the authors of CLRS indicate that an algorithm can be created that runs in time $O(|V||E|)$ by doing a DFS from each vertex and if each DFS yields only tree and back edges then the graph is singly connected. The authors of the preprint then proceed to provide an algorithm for dense graphs that runs in $O(|V|^)$ . They state and prove the following theorem: Theorem 2.1: Let $H$ be a strongly connected graph. $H$ is not singly connected iff at least one of the following conditions holds. The DFS search either yields a cross edge, a forward edge, or a vertex $v$ such that from the subtree rooted at $v$ , there are at least two back edges to proper ancestors of $v$ Given this theorem, I'm a bit confused about the algorithm provided by CLRS. CLRS states that as long as the search only yields tree and back edges, the graph is singly connected. However, it would seem that the theorem above provides another case that CLRS do not consider. Namely, a vertex $v$ such that from the subtree rooted at $v$ , there are at least two back edges to proper ancestors of $v$ . The definition for a singly connected graph provided by CLRS seems to be inclusive enough to include the kind of graph the preprint is considering, so I'm confused how to reconcile them. What am I missing here? Also, how does the CLRS algorithm run in time $O(|E||V|)$ ? Wouldn't it be $O(|V|(|V|+|E|))$ ? Here's the case I have in mind:
Note that the algorithm by CLRS runs DFS for each vertex separately. Therefore, for the case you mentioned, the algorithm declares the graph as non-singly connected when performing DFS starting from the vertex $v$ . In that case, one of the back edges will be a cross-edge in the DFS tree, thus declaring the graph as not singly connected.
Please note that, CLRS algorithm in a single DFS call, checks if the root vertex has at most one simple path to each of the other vertices; that's all.
And, yes I too believe that the running time complexity of CLRS algorithm should be $O(|V| (|V| + |E|))$ . The running time complexity of $O(|V||E|)$ is incorrect since for the case when $|E| = 0$ it implies that the complexity is $O(1)$ ; however the algorithm must visits each vertex at least once.
