<p>The problem is NP-hard, even in just two dimension, by reduction from the <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">knapsack problem</a>.</p>
<p>Consider a 0-1 knapsack instance with <span class="math-container">$n$</span> items, where the weight of the <span class="math-container">$i$</span>th item is <span class="math-container">$w_i$</span> and its value is <span class="math-container">$v_i$</span>.  Build a graph with <span class="math-container">$n+1$</span> vertices, with one edge from the <span class="math-container">$i$</span>th vertex to the <span class="math-container">$i+1$</span>st vertex of weight <span class="math-container">$(0,0)$</span> and another of weight <span class="math-container">$(w_i,-v_i)$</span>.  Now to test whether there exists a solution to the knapsack instance with total weight <span class="math-container">$\le W$</span> and total value <span class="math-container">$\ge V$</span>, check whether there exists a path in the graph from the first vertex to the last vertex whose cost is <span class="math-container">$\le (W,-V)$</span>.</p>

CC BY-SA 4.0
2024-03-16T05:38:17.977Z
2024-03-16T05:38:17.977Z
D.W.
<p>Consider a generalisation of the shortest path problem on directed graphs with weights in <span class="math-container">$\mathbb{Q}^k$</span>. Formally, the input is a graph, a source state <span class="math-container">$s$</span>, a target state <span class="math-container">$t$</span>, and an objective vector <span class="math-container">$\vec{o}$</span>. The goal is to determine whether there is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in the graph whose cost <span class="math-container">$\vec{c}$</span> (obtained by summing the weights at each transition) is smaller or equal than <span class="math-container">$\vec{o}$</span> (componentwise).</p>
<p>It is easy to show that the problem is in NP. The problem with equality <span class="math-container">$\vec{c} = \vec{o}$</span> is NP-complete (from <a href="http://www.numdam.org/item/ITA_1997__31_5_429_0.pdf" rel="nofollow noreferrer">this paper</a>). On the other hand, the problem with inequality <span class="math-container">$c \le o$</span> for dimension one is solvable in polynomial time using the shortest path algorithm.</p>
<p>Is there a polynomial time algorithm for the inequality version of the problem?</p>

CC BY-SA 4.0
2024-03-16T12:27:37.900Z
This is a standard problem called the multi-objective shortest path problem, and as noted in the the answers, it is NP-Hard for even two dimensions via a reduction from Subset Sum or Knapsack.
Chandra Chekuri
<ds.algorithms><graph-theory><np-hardness><shortest-path>
Shorter than target vector path algorithm
user1868607
# Shorter than target vector path algorithm

(Asked by: username_0 on 2024-03-15)

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective vector $\vec{o}$. The goal is to determine whether there is a path from $s$ to $t$ in the graph whose cost $\vec{c}$ (obtained by summing the weights at each transition) is smaller or equal than $\vec{o}$ (componentwise).

It is easy to show that the problem is in NP. The problem with equality $\vec{c} = \vec{o}$ is NP-complete (from [this paper](http://www.numdam.org/item/ITA_1997__31_5_429_0.pdf)). On the other hand, the problem with inequality $c \le o$ for dimension one is solvable in polynomial time using the shortest path algorithm.

Is there a polynomial time algorithm for the inequality version of the problem?

**Tags:** ds.algorithms, graph-theory, np-hardness, shortest-path
> **Comments:**
> **username_1**: This is a standard problem called the multi-objective shortest path problem, and as noted in the the answers, it is NP-Hard for even two dimensions via a reduction from Subset Sum or Knapsack.  

---

## 1 answers

### Answer by username_2 on 2024-03-16. Score: 1 | Accepted answer

The problem is NP-hard, even in just two dimension, by reduction from the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem).

Consider a 0-1 knapsack instance with $n$ items, where the weight of the $i$th item is $w\_i$ and its value is $v\_i$. Build a graph with $n+1$ vertices, with one edge from the $i$th vertex to the $i+1$st vertex of weight $(0,0)$ and another of weight $(w\_i,-v\_i)$. Now to test whether there exists a solution to the knapsack instance with total weight $\le W$ and total value $\ge V$, check whether there exists a path in the graph from the first vertex to the last vertex whose cost is $\le (W,-V)$.


---

