# Is there an algorithm to find the lengths of all paths from a given vertice that can run in polynomial time?

I have seen from a few sources (such as the CS Stack Exchange) that the problem of determining all the paths between two vertices $$u$$ and $$v$$ is NP hard. However, foR something that I am developing, I need to find only the number of paths of a given length whose first vertice is $$v$$. Is there an algorithm that can find this in Polynomial time ?

P.S. This is the first time I am posting on Stackexchange, so I apologize in case my question is too "rough" .

• I object to marking the question as "too broad". The question looks pretty specific. Dec 28, 2018 at 10:31

If you only need the number of walks of a given length, you can do it in polynomial time (with respect to the number of vertices of the graph) using the incidence (or adjacency) matrix of the graph.

Indeed, assume $$G= (V,E)$$ is the graph in question, where $$|V| = n$$ and $$A$$ is the incidence matrix of $$G$$, i.e. $$A$$ is an $$n\times n$$ matrix of $$\{0,1\}$$-s where $$(i,j)$$-th element is $$1$$ iff there is an edge from vertex $$i$$ to vertex $$j$$.

Fix an integer $$k \geq 1$$, which is the length of the walk. It is a well-known fact that the $$(i,j)$$-th entry of the matrix $$A^k$$ shows the number of walks from $$i$$ to $$j$$ having length $$k$$ (the proof follows by a straightforward induction on $$k$$ and the definition of a matrix product, see wikipedia for instance).

Getting back to your original question: $$A^k$$ can be computed in $$O(n^3 + n\log k)$$ time using singular value decomposition (SVD). Here $$n^3$$ is the time to complete the SVD and $$n \log k$$ is the time to raise all elements on the diagonal matrix of the SVD into power $$k$$. See here for further discussion. Once you have $$A^k$$, then summing over all elements of the $$v$$-th row ($$v$$ was the vertex where you start the walk of length $$k$$) gives the number of walks from $$v$$ having length $$k$$.

For the number of paths (instead of walks), see the other answer.

• Just to note: even the most straightforward way is polynomial-time, with single matrix product in $O(n^3)$, thus $O(k n^3)$ for $A^k$, or $O(\log_2 k \cdot n^3)$ if using exponentiation by squaring. SVD, though, may suffer from precision issues. Dec 28, 2018 at 10:28
• @lisyarus, thanks for your comment. Well, of course the straightforward matrix product is still polynomial in $n$ (assuming $k$ is fixed). I though of SVD only to remove the factor coming from $k$ from the polynomial on $n$, but I suppose there should be better approaches here.
– Hayk
Dec 28, 2018 at 10:39
• @Hayk Does this calculate the number of paths between $i$ and $j$ though, or the number of walks between $i$ and $j$. A walk may have cycles and it may even backtrack on an edge.
– Mike
Dec 28, 2018 at 19:16
• In fact the above answer is incorrect: If it were true you could use the above to count the number of paths between $i$ and $j$: Simply take the sum $\sum_k A^k_{ij}$.. However, finding the number of such paths is NP-Hard.
– Mike
Dec 28, 2018 at 19:24
• @Mike, fair enough, it was an oversight from my part: "walk" vs "path". Indeed, my answer computes the number of walks rather than the number of paths, there's no restriction on $A^k$ to take into account distinct vertices only. The answer is now edited accordingly.
– Hayk
Dec 28, 2018 at 20:02

No, there is no such algorithm, unless P=NP. More precisely: If determining the number of path between two vertices $$u$$ and $$v$$ is NP-Hard, then so is calculating the number of paths starting at any vertex $$v$$.

Indeed, let $$G$$ be a graph, and $$u$$ and $$v$$ any two vertices in $$G$$. Then write as $$n_G(v)$$ the number of paths starting at $$v$$ and write as $$n_G(v,u)$$ the number of paths starting at $$v$$ and ending at $$u$$. Next, let $$G'$$ be the graph formed from $$G$$ by adding an extra vertex $$z$$ and attaching that extra vertex to precisely $$u$$. Then $$n_G(v)+ n_G(v,u) = n_{G'}(v)$$. If we can calculate $$n_G(v)$$ and $$n_{G'}(v)$$ in polynomial time then we can calculate $$n_{G}(v,u)$$ in polynomial time.

And if we can calculate the number $$^kn_G(v)$$ of paths of length $$k$$ starting at $$v$$ then we can certainly calculate $$n_G(v)$$; indeed take the sum $$\sum_k$$ $$^kn_G(v)$$ to get $$n_G(v)$$.

[Computing the total number of walks of a given length $$k$$ between two vertices is easy to do in polynomial time however; the above answer shows how to do this.]