The complexity of a multi-objective shortest path problem

Question

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?

Answer 1

It is NP-hard by reduction from Partition.

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.)