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?

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 19 '17 at 16:28
  • $\begingroup$ " we want to go from place A to place B quickly as possible" and " we need to find a route with at most t minutes" are not the same. Which is it? $\endgroup$ – Raphael Dec 19 '17 at 16:29
  • $\begingroup$ If every edge has two costs, this is not simply Dijkstra, as there may be many "closest" nodes. $\endgroup$ – Albert Hendriks Dec 20 '17 at 18:20

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.