<p>It is NP-hard by reduction from <a href="http://en.wikipedia.org/wiki/Partition_problem" rel="nofollow">Partition</a>.</p>

<p>Let $x_1,\dots,x_n$ be the partition instance.</p>

<p>Create a graph on levels $0,1,\dots,n$ with level $0$ containing the start vertex $s$, and level $i$ containing two vertices, $a_i$ and $b_i$.</p>

<p>Every path from $s$ to a vertex in the last level corresponds to a partition of $x_1,\dots,x_n$ into two blocks, $A$ and $B$, as follows:
If the path goes through $a_i$, then $x_i$ is placed in $A$, otherwise the path must go through $b_i$, and $x_i$ is placed in $B$.
Conversely, every partition is realized by some path in this way.</p>

<p>For every edge to $a_i$ from the level below, let the cost be $(x_i,0)$, and for every edge to $b_i$ from the level below, set the cost to $(0,x_i)$.
Finally, set $L_i = \sum_{i=1}^n x_i/2$.
Now the partition instance has a balanced partition if and only if there is a solution to the path problem with cost $\le \sum_{i=1}^n x_i/2$.</p>

<p>(Edit: I originally gave a reduction from the shortest weight-constrained path problem, and then to answer a comment; a reduction from partition to the shortest weight-constrained path problem. However, the last reduction is enough by itself.)</p>

CC BY-SA 3.0
2015-02-07T09:35:11.183Z
Thank you. Very nice and simple in the end. I notice the Knapsack reduction (in the now deleted answer) was similarly simple as well.
Simd
CC BY-SA 3.0
2015-02-03T09:41:18.593Z
2015-02-05T12:38:30.513Z
2015-02-05T12:38:30.513Z
hal46
<p>I have the following shortest path problem.</p>

<p>Consider a directed graph with $n$ levels.  Each level has $m$ nodes.  Each node at level $i$ is connected to all nodes at level $i+1$.  Let us also make a starting node that is connected to all nodes at level $1$ (the first level). </p>

<p>Each edge is labelled by a pair of non-negative integer weights.  Each level $i$ has a single non-negative integer label which we call $L_i$.  </p>

<p>The goal is to minimize the shortest path with respect to the first weight in each edge weight pair from the starting node to the last level while ensuring that the weight of the path from the starting node with respect to the second weight in each edge weight pair is no more than $L_i$ at each level $i$.</p>

<p>Has this problem been studied? Is it known to be NP-hard?</p>

CC BY-SA 3.0
2015-01-29T12:30:07.273Z
This problem is actually sort of [constrained shortest path](https://en.wikipedia.org/wiki/Constrained_Shortest_Path_First) problem, which is NP-complete on DAGs (For your DAG is also NP-complete except if weight functions are not arbitrary functions).
Saeed
CC BY-SA 3.0
2015-01-29T14:03:44.977Z
@Saeed This is very interesting. Do you have a suitable reference for the NP-hardness result by any chance?  My weights are all non-negative integers. I am not sure what you meant precisely by " except if weight functions are not arbitrary functions".
Simd
CC BY-SA 3.0
2015-01-29T14:35:07.423Z
In the Gary and Johnson's book is written the proof is by personal communication but I have my own proof which maybe be the same as others but if you want to have a reference to something you may use this paper which also has a nice and quite simple (to implement) FPTAS, but it's not exactly what are you searching for but you can modify it (But just referred to the book for NP-hardness and if you look at the book you will see what I said). http://www.sciencedirect.com/science/article/pii/S0020019002002053.
Saeed
CC BY-SA 3.0
2015-01-29T14:39:09.293Z
By my except I mean if for example weight functions are not polynomially bounded by size of the graph. e.g if biggest weight is $n$ where $n$ is the number of nodes in the graph then we can solve the problem by dynamic programming in O(n^3).
Saeed
CC BY-SA 3.0
2015-01-29T15:01:26.113Z
@Saeed I can see a pseudo poly time dynamic programming solution but mine is $O(nm^2 L)$ where $L$ is the largest $L_i$.  How do you get it down to your complexity?
Simd
CC BY-SA 3.0
2015-01-29T15:15:55.103Z
I missed the factor $n$ (or L). It's n^4 in my example. Anyhow the pseudo polynomial time algorithm is trivial (homework question) the FPTAS is not very trivial and the proof of correctness of the FPTAS (with its running time) in the above paper is not trivial. But it's simple to use. Edit: OK I checked the question and I noticed that I didn't miss anything, I supposed $m = sqrt n$ and I wrote $O(n^3)$ if we translate it by your words they are same.
Saeed
CC BY-SA 3.0
2015-01-29T20:38:52.827Z
@Saeed Am I right in thinking that you haven't provided a reference for a proof of the NP-hardness of the OP's specific problem?
Simd
CC BY-SA 3.0
2015-01-29T21:11:35.843Z
@Lembik, yes you are right.
Saeed
<cc.complexity-theory><reference-request><graph-theory><np-hardness>
The complexity of a multi-objective shortest path problem
Simd
# The complexity of a multi-objective shortest path problem

(Asked by: username_0 on 2015-01-29)

I have the following shortest path problem.

Consider a directed graph with $n$ levels. Each level has $m$ nodes. Each node at level $i$ is connected to all nodes at level $i+1$. Let us also make a starting node that is connected to all nodes at level $1$ (the first level).

Each edge is labelled by a pair of non-negative integer weights. Each level $i$ has a single non-negative integer label which we call $L\_i$.

The goal is to minimize the shortest path with respect to the first weight in each edge weight pair from the starting node to the last level while ensuring that the weight of the path from the starting node with respect to the second weight in each edge weight pair is no more than $L\_i$ at each level $i$.

Has this problem been studied? Is it known to be NP-hard?

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness

> **Comments:**
> **username_1**: This problem is actually sort of [constrained shortest path](https://en.wikipedia.org/wiki/Constrained_Shortest_Path_First) problem, which is NP-complete on DAGs (For your DAG is also NP-complete except if weight functions are not arbitrary functions).  
> **username_0**: @username_1 This is very interesting. Do you have a suitable reference for the NP-hardness result by any chance?  My weights are all non-negative integers. I am not sure what you meant precisely by " except if weight functions are not arbitrary functions".  
> **username_1**: In the Gary and Johnson's book is written the proof is by personal communication but I have my own proof which maybe be the same as others but if you want to have a reference to something you may use this paper which also has a nice and quite simple (to implement) FPTAS, but it's not exactly what are you searching for but you can modify it (But just referred to the book for NP-hardness and if you look at the book you will see what I said). http://www.sciencedirect.com/science/article/pii/S0020019002002053.  
> **username_1**: By my except I mean if for example weight functions are not polynomially bounded by size of the graph. e.g if biggest weight is $n$ where $n$ is the number of nodes in the graph then we can solve the problem by dynamic programming in O(n^3).  
> **username_0**: @username_1 I can see a pseudo poly time dynamic programming solution but mine is $O(nm^2 L)$ where $L$ is the largest $L_i$.  How do you get it down to your complexity?  
> **username_1**: I missed the factor $n$ (or L). It's n^4 in my example. Anyhow the pseudo polynomial time algorithm is trivial (homework question) the FPTAS is not very trivial and the proof of correctness of the FPTAS (with its running time) in the above paper is not trivial. But it's simple to use. Edit: OK I checked the question and I noticed that I didn't miss anything, I supposed $m = sqrt n$ and I wrote $O(n^3)$ if we translate it by your words they are same.  
> **username_0**: @username_1 Am I right in thinking that you haven't provided a reference for a proof of the NP-hardness of the OP's specific problem?  
> **username_1**: @Lembik, yes you are right.  

---

## 1 answers

### Answer by username_2 on 2015-02-03. Score: 5 | Accepted answer

It is NP-hard by reduction from [Partition](http://en.wikipedia.org/wiki/Partition_problem).

Let $x\_1,\dots,x\_n$ be the partition instance.

Create a graph on levels $0,1,\dots,n$ with level $0$ containing the start vertex $s$, and level $i$ containing two vertices, $a\_i$ and $b\_i$.

Every path from $s$ to a vertex in the last level corresponds to a partition of $x\_1,\dots,x\_n$ into two blocks, $A$ and $B$, as follows:
If the path goes through $a\_i$, then $x\_i$ is placed in $A$, otherwise the path must go through $b\_i$, and $x\_i$ is placed in $B$.
Conversely, every partition is realized by some path in this way.

For every edge to $a\_i$ from the level below, let the cost be $(x\_i,0)$, and for every edge to $b\_i$ from the level below, set the cost to $(0,x\_i)$.
Finally, set $L\_i = \sum\_{i=1}^n x\_i/2$.
Now the partition instance has a balanced partition if and only if there is a solution to the path problem with cost $\le \sum\_{i=1}^n x\_i/2$.

(Edit: I originally gave a reduction from the shortest weight-constrained path problem, and then to answer a comment; a reduction from partition to the shortest weight-constrained path problem. However, the last reduction is enough by itself.)

> **Comments:**
> **username_0**: Thank you. Very nice and simple in the end. I notice the Knapsack reduction (in the now deleted answer) was similarly simple as well.  

---

