# Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

I am trying to find the fastest algorithm to find all the possible paths of length $$N$$ from a given node in a directed graph.

My solution is to do a modification of breadth first search from the given node for $$N$$ iteration. Its time complexity is around $$\theta(V+E)$$. But the problem is $$|V|$$ & $$|E|$$ becomes exponential because as long as there is an edge, the same node can be visited again.

Can there be a solution of this problem with polynomial time complexity? It seems this problem has optimal substructure solution. Is there any solution using dynamic approach?

• How would V and E be exponential? Oct 25 '19 at 8:38
• @oerpli Paths allowed in every directions. I am not coloring the nodes unlike BFS. I can visit the same node again as long as there is an edge. Oct 25 '19 at 8:50
– user35837
Oct 25 '19 at 9:20

This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero.

This problem is actually #P-hard wich is believed to be strictly harder than NP.

The version of the problem where you only look for the existence of such a path is called the longest path problem. A well-known problem in theory. It is fixed-parameter tractable when parameterized by the length of the path (check Parameterized Algorithms book by Cygan et al for description and methods).

• Your answer does help me. Give me some more time to think on this. Oct 25 '19 at 16:03
• There are also a couple or randomized approximations for counting Hamiltonian Cycles. I don't know how applicable they are for your case. Oct 25 '19 at 16:03
• Please share whatever relevant you can share. Oct 25 '19 at 16:05
• ieeexplore.ieee.org/abstract/document/336517 Oct 25 '19 at 16:06
• ieeexplore.ieee.org/abstract/document/336517 Oct 25 '19 at 16:07

The above answer considers the version of this problem where vertices cannot be visited multiple times. However it seems that the intention of the question is that vertices could be visited multiple times.

The number of such paths can be exponential in |V| and |E|, so they cannot be listed in polynomial time.

The problem of counting the number of such paths is equivalent to computing the $$N$$th power of the adjacency matrix of the graph. If $$A$$ is the adjacency matrix of the graph, then the value of the cell $$(i, j)$$ of $$A^N$$ is the number of $$N$$-length paths from vertex $$i$$ to vertex $$j$$.

While in general such paths cannot be listed in polynomial time, they however can be listed with polynomial delay (i.e. outputting a new path in polynomial time). For all lengths $$k \le N$$, compute by dynamic programming numbers $$cnt[v][k]$$, which represents the number of paths of length $$k$$ from the starting vertex to vertex $$v$$. Now such paths can be extracted by traversing this dynamic programming structure backwards. If $$cnt[v][N]$$ is positive, find vertex $$u$$ such that there is edge from $$u$$ to $$v$$, and $$cnt[u][N-1]$$ is positive. Extract the $$N-1$$ length path to $$u$$ recursively, add $$v$$ as the last vertex of the path and subtract $$cnt[v][N]$$ by one.

• +1. Yeah. The solution I came up with Using dynamic programming didn't reduce the time but it was actually giving new path in polynomial delay. Thanks to give me clarity. :) Oct 26 '19 at 16:29