Optimal path with multiple costs

MathOverflow Asked by lchen on November 18, 2020

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1le ile k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=sum_{ein 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_{Pin{cal P}_{st}} max_{1le ile k} c_i(P)$$

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

2 Answers

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$}\ 1 &text{otherwise}end{cases} && text{for $iin 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 $rin{1,dots,k}$} end{align}

Answered by RobPratt on November 18, 2020

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

Answered by Mikhail Tikhomirov on November 18, 2020

Add your own answers!

Related Questions

Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP