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 ?

  • 6
    $\begingroup$ It is in P: compute the $K$th power of the adjacency matrix by repeated squaring, capping all entries by $1$. $\endgroup$ – Emil Jeřábek Apr 4 '18 at 20:46
  • $\begingroup$ You can also simply do a BFS starting from vertex $s$ and check if you reach $t$ in $K$ steps or not. $\endgroup$ – karmanaut Apr 7 '18 at 19:21