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

Question

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?

Answer 1

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).

Answer 2

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.