Shorter than target vector path algorithm

Question

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

Answer 1

The problem is NP-hard, even in just two dimension, by reduction from the 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)$.