Shortest walk that covers $k$ nodes
There is a simple reduction from Hamiltonian path. Suppose we are given a graph $G$ on $n$ vertices, and want to know whether it contains a Hamiltonian path. Adjoin a new vertex $s$ and connect it to all other vertices. The new graph $G'$ contains a walk of length (at most) $n$ starting at $s$ and covering all vertices if and only if the original graph $G$ contains a Hamiltonian path.