Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$).

Since your problem can be reduced to Dijkstra's algorithm in at most polynomial time, it is not NP-complete.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.