# Decision if there exists a path between $s$ and $t$ of length $k$

I conisder a problem:

It is given a graph $G$, vertices $s,t$, $k$- length of the graph. Prove that decision whether there is a path between $s$ and $t$ of length $k$ is NP-complete.

Please note that in our problem we have a path, not a **simple path* **

*It is trivial when we have a simple path (define as sequence of vertices where every vertice occurs at most once (there is no cycle) ).

I don't know how to start. I cannot come up what's problem I should reduce. Please hint me.

• So $k$ is a vertex or the length? – Romantic Electron Aug 13 '17 at 15:49
• If $k$ is $|V|+1$, isn't this the same as Hamiltonian cycle? – rus9384 Aug 14 '17 at 17:06
• @DavidRicherby: If the OP really meant "not-necessarily-simple path" (= "walk"), then she's mistaken that it's NP-complete: just raise the adjacency matrix to the $k$-th power, and see if the element at row $s$, column $t$ is zero or not. (She's also wrong that it's "trivial" in the simple path case. I suspect the question is about simple paths.) – j_random_hacker Aug 15 '17 at 17:03
• @j_random_hacker, You solved the problem! :) – Carol Aug 15 '17 at 19:24
• @j_random_hacker Turns out that's the answer, so please post it as one! :-) – David Richerby Aug 16 '17 at 13:52

## 1 Answer

I think you (or whoever asked you this question) probably does mean "simple path" (that is, a path that does not contain any vertex more than once), since this problem is indeed NP-hard.

If paths that may repeat vertices (often called "walks") are permitted, the problem is not NP-hard any more: It can be solved in polynomial time using matrix multiplication. Specifically, if $A$ is the adjacency matrix of the graph, then $A^k[i, j]$ (the element at row $i$, column $j$ in the matrix $A$ raised to the $k$-th power) is the number of walks of length exactly $k$ from $v_i$ to $v_j$. You can compute $A^k$ in $O(n^3 \log k)$ time using exponentiation by squaring.