2
$\begingroup$

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|^{2})$. 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: enter image description here

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I'm having trouble formally proving that this would always be the case (i.e., that traversing from node v would always result in a cross or forward edge). Can you offer any suggestions? $\endgroup$
    – Hugh Mann
    Nov 15, 2023 at 22:12
  • $\begingroup$ @HughMann Did you understand it for the figure case that you mentioned in the question? $\endgroup$ Nov 16, 2023 at 7:29
  • $\begingroup$ Yes, I understood that case. After thinking about it, I think what I was actually looking for is a proof of correctness for the CLRS algorithm $\endgroup$
    – Hugh Mann
    Nov 16, 2023 at 19:52
  • 1
    $\begingroup$ @HughMann In the answer above, I have mentioned that: "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." Please think on this statement. This is the proof of correctness for CLRS algorithm. $\endgroup$ Nov 16, 2023 at 20:01
1
$\begingroup$

After doing more research, I believe the author of the preprint wasn't clear on the algorithm provided by CLRS. I think what CLRS meant is the following: for each $u \in V$ , run DFS-VISIT(u). In particular, we only visit all nodes in the DFS tree rooted at $u$; we do not visit other trees. This indeed provides a $O(|V||E|)$ algorithm to determine whether a graph $G$ is singly connected. Since DFS-VISIT(u) $\in O(|E|)$ and we need to check all nodes in the worst case, the overall time complexity is $O(|V||E|)$. Here's the full explanation: https://www3.cs.stonybrook.edu/~cse548/548hw5sol.pdf

$\endgroup$
1
  • 1
    $\begingroup$ More prcecisely, $DFS-VISIT(u) \in O(|E|+1)$. Note that when the vertex is a singleton vertex, we need to at least, visit the vertex, therefore $+1$ in the complexity, to make it correct for all cases. $\endgroup$ Nov 17, 2023 at 14:18

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .