# Is the search for a k-Hamiltonian Path NP-hard?

A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors.

This is an Hamiltonian Path:

This is a 3-Hamiltonian Path:

How would you prove that searching for a k-Hamiltonian Path is also NP-hard (if it is)?

Any algorithm that can solve the $k$-Hamiltonian path problem must, in particular, be able to solve the case $k=1$, which is just an ordinary Hamiltonian path. We can obviously verify a claimed $k$-Hamiltonian path in polynomial time, so the problem remains in NP. Therefore, $k$-Hamiltonian path is NP-complete.
• The general case is always at least as hard as any specific case, since being able to solve the general case means you must be able to solve every specific case. There's not really anything more to say than the sentence you quoted: if problem $X$ has an NP-complete problem as a special case, then there's a near-trivial reduction from that NP-complete problem to $X$ so, if $X$ is in NP (i.e., it's not so general that its complexity is higher) then it's NP-complete by definition. – David Richerby Feb 28 '17 at 11:30
• I see, thanks! Mmmh... so, if we have an algoritmh that solves, as example, only the $3$-Hamiltonian path problem, we can only say that it is in a class lower than NP-complete. We can't deduce anything more, right? – Luca Feb 28 '17 at 11:41