# Constrained shortest path (NP?)

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?

-
Are you asking if the problem is in NP or NPC ? – Belgi Aug 6 '12 at 21:59
This is not a decision problem. However "do there exist such paths...with total cost $\le c$?" is very obviously in NP (the paths themselves are a polynomial certificate). Given that you ask about "translating" to another problem, perhaps you meant something else... – Erick Wong Aug 6 '12 at 21:59
I'm sorry I meant to ask if the problem is in NPC. I just want to know if there exists a polynomial time algorithm for this problem. If not, is the problem in NPC and to which other problem(s) in NPC it's similar. – sjoerd999 Aug 8 '12 at 8:17

Your problem has at most a polynomial time difference from Dijkstra's algorithm. Dijkstra's algorithm will give you the shortest path from a single source node to multiple destination nodes. Your algorithm rejects any path greater than a particular length (note that your lower bound should probably be 2). This is a straightforward constraint to add: While finding the shortest path, you will also test that the depth of any path does not exceed length $k$, where $k$ is your upper bound constraint. Since Dijkstra's uses a BFS, this implementation should have better average running time than Dijkstra's (it will reject a path as soon as its depth exceeds $k$).