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
    Commented 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
    Commented Jun 27, 2018 at 11:03

2 Answers 2

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$
0
$\begingroup$

Are you interested in listing all paths or just counting them?

Counting is rather easy and can be done in O(Vk) time: Augment your graph so all paths are of length k. For example let's assume you have a path of length k-1. What you would do is add a vertex with 1 incoming degree and 1 outgoing degree connecting the last node before the sink and the sink, et voila - it's of length k. We are essentially constructing a multipartite graph and we would like to preserve an important property here for later - each node is in the jth stage of the this augmented graph if the longest path from source to it is of length j. You can perform this with an easy algorithm with time complexity O(Vk) or if you want a tighter bound given that each node has constant number of edges C O(C×V^2): Begin with frontier just the sink Every iteration i (initially i=1): Visit all nodes with incoming edges from the frontier. Set their value to i and add them to the next frontier.

At the end you will have the longest path to each node and that's the stage in the multipartite graph it will belong. To connect nodes that are no longer in neighbouring stages, simply add an augmented node as described above in each stage between them until they are connected Start from sink with value 1. Send this value to all vertices the sink is connected to. From here column by column by column: Sum all values received by a vertex. Send them to all vertices it is connected to. Continue until you have reached the sinks. This will give you the number of unique paths to each sink

The last algorithm can be avoided by just multiplying the connectivity matrix of each stage to its next one with the current values of the stages as a vector.

Improve this answer
$\endgroup$

Your Answer

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

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