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 problem in NP that contains an NP-complete problem as a special case is NP-complete.

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.