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?
Best Answer
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$).
Since your problem can be reduced to Dijkstra's algorithm in at most polynomial time, it is not NP-complete.