Return to Question

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. We seek a path that minimizes the maximal cost. Mathematically, we seek

$$P^*=\min_{P} \max_{1\le i\le k} c_i(P)$$

My question is: Is this problem related to some known NP-hard problem? How to prove the hardness?

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and $t$, we seek a path between them that minimizes the maximal cost. Mathematically, we seek

$$P^*=\min_{P\in{\cal P}_{st}} \max_{1\le i\le k} c_i(P)$$

My question is: Is this problem related to some known NP-hard problem? How to prove the hardness?

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. We seek a path that minimizes the maximal cost. Mathematically, we seek

$$P^*=\min_{P} \min_{1\le i\le k} c_i(P)$$

My question is: Is this problem related to some known NP-hard problem? How to prove the hardness?

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. We seek a path that minimizes the maximal cost. Mathematically, we seek

$$P^*=\min_{P} \max_{1\le i\le k} c_i(P)$$

My question is: Is this problem related to some known NP-hard problem? How to prove the hardness?