# Finding all unique paths from a source to a sink in a specially-formed DAG

Let $G$ be a directed, acyclic graph of order $n$, such that:

1. $G$ has exactly one source vertex $s$;
2. $G$ has exactly two sink vertices $t_1, t_2$;
3. The out-degree of any non-sink vertex in $G$ is exactly 2; and
4. The longest path from $s$ to either of $t_1,t_2$ has length $k$.

What is the most efficient way of finding all unique paths from $s$ to $t_1$ (or $t_2$, doesn't really matter in this case) in $G$? What would the time complexity of this algorithm be? It is acceptable to use $k$ as a parameter if that would produce a better analysis.

• There could be $2^k$ such paths (imagine two rows of $k$ vertices each, with each vertex having an edge to the two vertices in the column to its right; then at each vertex we have 2 possible edges to take next), so no algorithm can be better than $O(2^k)$ in the worst case. – j_random_hacker Feb 27 '18 at 12:10
• It depends on what you mean by "finding". The answer will be different if the output is the number of paths, a list of the paths, or a data structure which contains the number of paths and allows selecting one uniformly at random. – Peter Taylor Jun 27 '18 at 11:03