0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – j_random_hacker
    Feb 27, 2018 at 12:10
  • $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Jun 27, 2018 at 11:03

1 Answer 1

Reset to default
0
$\begingroup$

If you are interested enumerating all the unique paths, then a recursion would be suitable since it is a dag. Observe that suppose v is a non source vertex and has incoming arcs from X1,...,Xn then every path from the source through v needs to pass through X1,...,Xn. . So if you enumerated all the paths from the source to each of these vertices you simply need to append v to them to compute all the paths through v originating from the source. This computation can be done very efficiently via dynamic programming. The reason DP will work is precisely because none of the paths from source to X1,...,Xn would have contained v since it is a dag.You should be able to work out the time complexity for the algorithm i described easily since it has a standard dp structure.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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