Optimal path with multiple costs

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

Answer 1

When $k \geq 2$ we can reduce from the NP-hard partition problem. For a given multiset $S = \{s_1, \ldots, s_n\}$ with even sum $X = \sum_{i = 1}^n s_i$ create $n + 1$ vertices $s = v_0, \ldots, v_n = t$, and for each $i = 0, \ldots, n - 1$ connect vertices $v_i$ and $v_{i + 1}$ by two paths of costs, say, $(2, 2 + s_i)$ and $(2 + s_i, 2)$ (to avoid multiple edges). Then a partition of $S$ exists iff $P^* = 2n + X / 2$.

Answer 2

This doesn't answer the NP-hardness, but you can solve the problem via integer linear programming as follows. For $(i,j)\in E$, let binary decision variable $x_{i,j}$ represent the flow from $i$ to $j$. The problem is to minimize $z$ subject to: \begin{align} \sum_{(i,j)\in E} x_{i,j} - \sum_{(j,i)\in E} x_{j,i} &= \begin{cases} 1 &\text{if $i=s$}\\ -1 &\text{if $i=t$}\\ 0 &\text{otherwise}\end{cases} && \text{for $i\in V$}\\ x_{i,j} &\in \{0,1\} &&\text{for $(i,j)\in E$}\\ z &\ge \sum_{(i,j)\in E} c_{i,j}^r x_{i,j} &&\text{for $r\in\{1,\dots,k\}$} \end{align}