Finding all paths from s to t in linear time
The algorithm you describe cannot possibly be linear time for a DAG or general graph. Consider the following DAG on $n$ vertices $V = \{v_1, v_2, \ldots v_n\}$. Take a particular node $v_i$, for all $j &gt; i$ add an edge $(v_i, v_j)$. This will create $\Theta(n^2)$ edges in this DAG. Note that a path from $v_1$ to $v_n$ can use any subset of nodes $\{v_2, v_3, \ldots v_{n-1}\}$. That is to say there are $2^{n-2}$ possible paths from $v_1$ to $v_n$. Clearly to print all these would take exponential time.



What you can do in linear time, is determine the subgraph that would contain all possible paths from $s$ to $t$. With a source $s$ in mind, we first check if it can reach $t$ (via DFS), if not then return an empty subgraph. Otherwise we check if $s$'s children $\{v_1, v_2, \ldots\}$ can reach $t$, this can be done recursively top-down or bottom-up if we start at $t$ and work backwards. Let's say $A$ is the set of nodes who are a descendant of $s$ and an ancestor of $t$. $A$ will also include $s$ and $t$ for obvious reasons. The subgraph we are interested will contain exactly the vertices in $A$. With this we can iterate through edges an include them as necessary, or we could even pick up edges long the way as we are determining which nodes are in $A$. This procedure overall will take $O(n + m)$. Of course, this is only interesting in a DAG unless $t$ or $s$ is an articulation point.