Can Santa be both fair and efficient?
I am slightly confused. If $k$ is a constant, then you can try all $O(n^k)$ possible tours. Hence the problem is in ${\sf P}$.

However, if $k$ is part of the input, the decision problem is ${\sf NP}$-complete. This can be shown by reducing $\text{HAM-CIRCUIT}$ to the problem, by the following reduction.

Assume that we want to determine if a $n$-vertex graph $G$ has a Hamiltonian circuit. Then we take the complete graph $K_n$ with the following distance function
$$
w_{ij}:=\begin{cases}
1 &amp; \text{if $(v_i,v_j)$ is an edge in $G$} \\
2 &amp; \text{otherwise}
\end{cases}.
$$
Furthermore we pick $k=n$ and $m=n-1$.

Let me tell you why this is a reduction. If $G$ has a Hamiltonian circuit, then there is a tour in $K_n$ with length $n$. In other words a circular route of length $\le n$ that serves $&gt; (n-1)$ nodes. On the other hand, if there is a Santa-tour that visits $&gt;(n-1)$ nodes is has to visit all nodes. Since the Santa-tour can only have length $\le n$ and every edge length is at least 1, all $n$ edges in this tour have length 1. Hence this tour corresponds to a Hamiltonian circuit in $G$.