1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So $k$ is a vertex or the length? $\endgroup$ – Romantic Electron Aug 13 '17 at 15:49
  • 2
    $\begingroup$ If $k$ is $|V|+1$, isn't this the same as Hamiltonian cycle? $\endgroup$ – rus9384 Aug 14 '17 at 17:06
  • 5
    $\begingroup$ @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.) $\endgroup$ – j_random_hacker Aug 15 '17 at 17:03
  • 1
    $\begingroup$ @j_random_hacker, You solved the problem! :) $\endgroup$ – Carol Aug 15 '17 at 19:24
  • 1
    $\begingroup$ @j_random_hacker Turns out that's the answer, so please post it as one! :-) $\endgroup$ – David Richerby Aug 16 '17 at 13:52
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.