2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I object to marking the question as "too broad". The question looks pretty specific. $\endgroup$
    – lisyarus
    Dec 28, 2018 at 10:31

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – lisyarus
    Dec 28, 2018 at 10:28
  • $\begingroup$ @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. $\endgroup$
    – Hayk
    Dec 28, 2018 at 10:39
  • $\begingroup$ @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. $\endgroup$
    – Mike
    Dec 28, 2018 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – Mike
    Dec 28, 2018 at 19:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – Hayk
    Dec 28, 2018 at 20:02
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .