0
$\begingroup$

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?

  • 0
    Are you asking if the problem is in **NP** or **NPC** ?2012-08-06
  • 2
    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...2012-08-06
  • 0
    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.2012-08-08

1 Answers 1