3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How would V and E be exponential? $\endgroup$ – oerpli Oct 25 '19 at 8:38
  • $\begingroup$ @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. $\endgroup$ – Mr. Sigma. Oct 25 '19 at 8:50
  • 1
    $\begingroup$ cs.stackexchange.com/questions/10949/…. See this if it help you. $\endgroup$ – Shiv Oct 25 '19 at 9:20
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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. :) $\endgroup$ – Mr. Sigma. Oct 26 '19 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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