I've got the following problem:
Given a graph $G = (V, E)$ with $V = v_1, \ldots, v_n$ and $E = e_1, \ldots , e_m$ with associated cost $c_1, ... , c_m$. The problem is to find the shortest path from one start vertex (s) to multiple targets $t_1, \ldots , t_k$ taking into account these costs. This is the shortest path problem. My problem is similar, but now with the constraint that the total number of vertices used by these shortest paths is $M$ $(0 \le M \le |V| - k - 1)$. If a vertex is used by multiple paths it only counts once for the constraint.
Is this problem in NP?
If so, to which problem does it translate easily?