I've got the following problem:

Consider a graph $G=(V,E)$ with $V=\{v_1,\ldots,v_n\}$, and edge-set $E=\{e_1,\ldots,e_m\}$, with associated costs $c_1,\ldots,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,\ldots,t_k\,$, taking into account these costs. This is the shortest path problem. So minimize the sum of total costs from $s$ to all $t_1, \ldots , t_k$.

My problem is similar, but now with the constraint that the total number of vertices (not counting $s$ and $t_1, \ldots ,t_k$) used by these shortest paths is bounded (upperbound) by an integer $M$ satisfying $0 \leqslant M \leqslant n - k - 1$. If a vertex is used by multiple paths, it only counts once for the constraint. So these paths can, together, use no more than $M$ vertices to go from $s$ to $t_1, \ldots, t_k$.

What is the complexity of this problem, is it polynomial or exponential? Is this problem NP-hard?

  • $\begingroup$ Is M a lower bound or an upper bound? If it's a lower bound, then TSP can be reduced to the problem by setting M = n and solving it for all pairs (s, t) one by one. $\endgroup$ – Vinayak Pathak Aug 8 '12 at 10:45
  • $\begingroup$ What exactly are you trying to minimize: The sum of the path lengths? The length of the longest shortest path? Or something else? $\endgroup$ – Jeffε Aug 8 '12 at 14:20
  • 1
    $\begingroup$ Previously asked on math.SE $\endgroup$ – Jeffε Aug 8 '12 at 21:29
  • 1
    $\begingroup$ it's the former case. — Wait...what? (1) Your original post suggests that you want k paths, each starting at $s$ and ending at a different target $t_i$, together using at most $M$ distinct vertices, with minimum total length. (2) But your comment to Danny suggests that you want one walk that starts at $s$, visits every target $t_i$, visits at most $M$ distinct vertices, and has minimum length. Which is it—one walk or k paths? $\endgroup$ – Jeffε Aug 8 '12 at 21:34
  • 1
    $\begingroup$ @sjoerd999: Yes, the precise formulation does matter. The two formulations I described involve different cost metrics, both of which are different from (3) find a subtree that contains the source $s$, the $k$ targets $t_i$, and at most $m$ other vertices, of minimum total weight. Please stick to one precise formulation of the problem. $\endgroup$ – Jeffε Aug 9 '12 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.