1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ What are restrictions on $P$? Is a $P$ with no edges allowed? Also the formula for $P^*$ seems to have a $\min$ instead of $\max$. $\endgroup$ Nov 10, 2020 at 5:03
  • $\begingroup$ @MikhailTikhomirov Thank you for pointing out the typo. I don't catch your question. $P$ is a path composed of edges, no other particular constraint. $\endgroup$
    – lchen
    Nov 10, 2020 at 5:29
  • $\begingroup$ Can $c_i(e)$ be negative? Does $P$ have to be vertex- or edge-simple? $\endgroup$ Nov 10, 2020 at 5:42
  • $\begingroup$ Consider the baseline case that $c_i(e)$ are positive and $P$ is vertex- and edge-simple. $\endgroup$
    – lchen
    Nov 10, 2020 at 5:57
  • $\begingroup$ If $c_i(e)$ are positive, then clearly a single-edge $P$ is optimal. $\endgroup$ Nov 10, 2020 at 6:01

2 Answers 2

0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you. Nice proof.Could you pls have a look at another problem I posed some days ago: I think the problem is NP-complete but fail to prove it. mathoverflow.net/questions/373109/… $\endgroup$
    – lchen
    Nov 11, 2020 at 1:34
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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