<p>I've got the following problem:</p>

<p>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$.</p>

<p>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$.</p>

<p>What is the complexity of this problem, is it polynomial or exponential? 
Is this problem <strong>NP</strong>-hard?</p>

CC BY-SA 3.0
2012-08-08T10:45:19.327Z
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.
Vinayak Pathak
CC BY-SA 3.0
2012-08-08T14:20:03.343Z
What exactly are you trying to minimize:  The sum of the path lengths?  The length of the longest shortest path?  Or something else?
Jeffε
CC BY-SA 3.0
2012-08-08T15:12:36.737Z
Ok let me try to be a bit more clear. I'm trying to minimize the total costs of the paths from s to t1, ... , tk. These paths can, together, use no more than M vertices to go from s to t1, ..., tk. So M is an upperbound.
sjoerd999
CC BY-SA 3.0
2012-08-08T15:15:42.803Z
@Jeffe: yes I posted this problem a few months ago on Math SE. My question then was a bit different. I asked if someone knew an algorithm to solve this problem. Unfortunately no one came up with a satisfying answer. I came up with a heuristic based on the k-shortest path algorithm but I'm still curious if this problem can be solved efficiently.
sjoerd999
CC BY-SA 3.0
2012-08-08T16:03:58.977Z
Are you asking for the shortest path which starts from $s$ and goes through all of $t_1, t_2, ..., t_n$?  Or do you want a number of shortest paths that start at $s$ and end at one of $t_1, t_2, ..., t_n$?  If it's the latter, you can just keep expanding nodes using djikstra's algorithm until all the end nodes have been expanded, and the complexity doesn't change no matter how large $n$ is.
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2012-08-08T17:01:53.443Z
@BlueRaja-DannyPflughoeft: it's the former case. So from $s$ to ALL targets $t1, ... ,tk$ with $k <= n$. I strongly suspect the problem is NP Complete but I'm not sure. If it is I'm also curious to which other problem in NPC it can be transformed in an easy way (of course to all in polynomial time but I think you know what I mean).
sjoerd999
CC BY-SA 3.0
2012-08-08T21:29:41.750Z
[Previously asked on math.SE](http://math.stackexchange.com/questions/88314/variation-on-shortest-path)
Jeffε
CC BY-SA 3.0
2012-08-08T21:34:26.313Z
_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?
Jeffε
CC BY-SA 3.0
2012-08-09T05:29:43.670Z
@Jeffe: Oh I'm sorry I see now that my comment was not correct. It doesn't matter what case, as long as all targets are visited. So you start at s and build a tree which has at least all the targets in it. If you don't consider the source and the targets, the tree can be at most M vertices big.
sjoerd999
CC BY-SA 3.0
2012-08-09T19:56:37.447Z
@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.**
Jeffε
<cc.complexity-theory><graph-theory><shortest-path>
A constrained shortest path problem. What is the complexity?
sjoerd999
# A constrained shortest path problem. What is the complexity?

(Asked by: username_0 on 2012-08-08)

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?

**Tags:** cc.complexity-theory, graph-theory, shortest-path
> **Comments:**
> **username_1**: 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.  
> **username_2**: What exactly are you trying to minimize:  The sum of the path lengths?  The length of the longest shortest path?  Or something else?  
> **username_0**: Ok let me try to be a bit more clear. I'm trying to minimize the total costs of the paths from s to t1, ... , tk. These paths can, together, use no more than M vertices to go from s to t1, ..., tk. So M is an upperbound.  
> **username_0**: @Jeffe: yes I posted this problem a few months ago on Math SE. My question then was a bit different. I asked if someone knew an algorithm to solve this problem. Unfortunately no one came up with a satisfying answer. I came up with a heuristic based on the k-shortest path algorithm but I'm still curious if this problem can be solved efficiently.  
> **username_3**: Are you asking for the shortest path which starts from $s$ and goes through all of $t_1, t_2, ..., t_n$?  Or do you want a number of shortest paths that start at $s$ and end at one of $t_1, t_2, ..., t_n$?  If it's the latter, you can just keep expanding nodes using djikstra's algorithm until all the end nodes have been expanded, and the complexity doesn't change no matter how large $n$ is.  
> **username_0**: @BlueRaja-DannyPflughoeft: it's the former case. So from $s$ to ALL targets $t1, ... ,tk$ with $k <= n$. I strongly suspect the problem is NP Complete but I'm not sure. If it is I'm also curious to which other problem in NPC it can be transformed in an easy way (of course to all in polynomial time but I think you know what I mean).  
> **username_2**: [Previously asked on math.SE](http://math.stackexchange.com/questions/88314/variation-on-shortest-path)  
> **username_2**: _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?  
> **username_0**: @Jeffe: Oh I'm sorry I see now that my comment was not correct. It doesn't matter what case, as long as all targets are visited. So you start at s and build a tree which has at least all the targets in it. If you don't consider the source and the targets, the tree can be at most M vertices big.  
> **username_2**: @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.**  

---

## 0 answers

