2
$\begingroup$

The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."

The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/

I feel like the author likely got the time complexity analysis wrong. I would have asked the author themselves, but from the discussion below, they don't really respond to questions. So, what is the correct time complexity analysis for this problem, and how to derive it?

$\endgroup$
2
$\begingroup$

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots n]$ is a permutation of $1\, \dots n$ and $i < j$ implies that a path from node $\operatorname{TS}[j]$ to $\operatorname{TS}[i]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum_{i=1}^{n}T(i).$$

Proof: If you call your function on $\operatorname{TS}[i]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}[j]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that

$$\{\text{Vertices Reachable from} \operatorname{TS}[j]\} \subseteq \{\operatorname{TS}[k] \;|\; k = j + 1, \dots n\}.$$

Moreover $(i, j) \in E \implies i < j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.

$\endgroup$
4
  • $\begingroup$ I'm not sure I understand your explanation. Lets say there are 3 neighbor vertices of vertex 0, then there should be 3 recursive call for subgraphs of size n-1. From your explanation, I think you only account for 1. $\endgroup$
    – Henry Wise
    Jan 16 '20 at 3:56
  • $\begingroup$ Edited, hoping to have been more clear. $\endgroup$
    – Guanaco96
    Jan 17 '20 at 1:12
  • $\begingroup$ I have read your proof over and over again and still not be able to jump from "calling the sam efunction on smaller instances of the same problem" to "satisfying the equation above". Can you clarify how you reach that equation? Also, I am unclear what topo sort has to do with anything here $\endgroup$
    – Henry Wise
    Jan 18 '20 at 2:53
  • $\begingroup$ The main idea is that from the edge labelled as $\operatorname{TS}[i]$ you can reach only $n - i $ other vertices, then when you recursively call the function on a vertex you are facing a lower-sized instance of the same problem, since the function basically ignore nodes that cannot be reached. $\endgroup$
    – Guanaco96
    Jan 19 '20 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.