<p>Given a directed graph G= (V,E), a pair of vertices s and t, a natural number K encoded in binary, whether the problem to decide there exists a path (<strong>not necessarily simple</strong>) from s to t of length K is NP-complete ?</p>

CC BY-SA 3.0
2018-04-04T20:46:59.810Z
It is in P: compute the $K$th power of the adjacency matrix by repeated squaring, capping all entries by $1$.
Emil Jeřábek
CC BY-SA 3.0
2018-04-07T19:21:44.917Z
You can also simply do a BFS starting from vertex $s$ and check if you reach $t$ in $K$ steps or not.
karmanaut
<graph-theory><np-hardness>
Is NP-complete the existence of paths of a given length in a directed graph?
user49123
# Is NP-complete the existence of paths of a given length in a directed graph?

(Asked by: username_0 on 2018-04-04)

Given a directed graph G= (V,E), a pair of vertices s and t, a natural number K encoded in binary, whether the problem to decide there exists a path (**not necessarily simple**) from s to t of length K is NP-complete ?

**Tags:** graph-theory, np-hardness

> **Comments:**
> **username_1**: It is in P: compute the $K$th power of the adjacency matrix by repeated squaring, capping all entries by $1$.  
> **username_2**: You can also simply do a BFS starting from vertex $s$ and check if you reach $t$ in $K$ steps or not.  

---

## 0 answers

