Paths in a graph with two kinds of costs

Question

A weighted graph $G= (V, E, W_1, W_2)$ has two cost functions $W_1, W_2 : E \rightarrow \mathbb{R}$. Each edge $e$ has two costs $W_1(e)$ and $W_2(e)$. We may think the costs as representing different resources, such as time and fuel. Similarly, a path $p =e_1, e_2, \dots e_n$ has two costs,

$$W_1(p) = \sum_i W_1(e_i) \qquad \text{and} \qquad W_2(p) = \sum_i W_2(e_i) \qquad$$

Consider the following decision problem: given two nodes $u, v \in V$ and two constants $c_1, c_2$, does there exist a path $p$ from $u$ to $v$ such that $W_1(p) \le c_1$ and $W_2(p) \le c_2$?

Is it NP complete or is a polynomial algorithm known to exist?

Answer 1

This is NP-hard by reduction from Partition.

Given an instance of the Partition problem consisting of $n$ nonnegative integer values $x_1, \dots, x_n$, we can generate an instance of your problem as follows:

• Make $n+1$ vertices $s_0, \dots, s_n$. Let $u = s_0$ and $v = s_n$.
• Make $n$ vertices $a_1, \dots, a_n$, and edges $s_{i-1}a_i$ for every $1 \le i \le n$ having weights $W_1(s_{i-1}a_i) = x_i$ and $W_2(s_{i-1}a_i) = 0$.
• Make another $n$ vertices $b_1, \dots, b_n$, and edges $s_{i-1}b_i$ for every $1 \le i \le n$ having weights $W_1(s_{i-1}b_i) = 0$ and $W_2(s_{i-1}b_i) = x_i$.
• Also add edges $a_is_i$ and $b_is_i$ having both weights 0 for every $1 \le i \le n$.
• Set $c_1 = c_2 = \frac{1}{2}\sum_{i=1}^n x_i$.

The original Partition instance has a solution if and only if the above-constructed instance of your problem has a solution. Basically, for each number $x_i$, we must visit exactly one of the vertices $a_i$ or $b_i$, incurring a cost of $x_i$ for one of the two weights (and zero cost for the other weight).