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?

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

1 Asked on November 12, 2021 by user6671

1 Asked on November 12, 2021 by steven-obua

1 Asked on November 12, 2021 by a-k-a-teru-san

ca classical analysis and odes integration legendre polynomials special functions

1 Asked on November 12, 2021 by tobias-fritz

1 Asked on November 12, 2021 by spoilt-milk

dg differential geometry lie algebras riemannian geometry tensor calculus

0 Asked on November 12, 2021

0 Asked on November 12, 2021

ag algebraic geometry harmonic analysis langlands conjectures nt number theory

1 Asked on November 12, 2021

ag algebraic geometry arithmetic geometry p adic hodge theory

1 Asked on November 9, 2021 by vova

1 Asked on November 9, 2021 by grok

0 Asked on November 9, 2021

algebraic systems invariant theory lo logic model theory universal algebra

0 Asked on November 9, 2021 by user161444

0 Asked on November 9, 2021

algebraic number theory fields galois theory nt number theory number fields

0 Asked on November 9, 2021 by as1

ap analysis of pdes brownian motion pr probability stochastic differential equations stochastic processes

0 Asked on November 9, 2021 by makt

0 Asked on November 9, 2021 by mohsen-shahriari

0 Asked on November 9, 2021

1 Asked on November 9, 2021 by sadok-kallel

arithmetic groups at algebraic topology gt geometric topology lattices

3 Asked on November 9, 2021 by squid-with-black-bean-sauce

ra rings and algebras reference request soft question textbook recommendation

1 Asked on November 9, 2021

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

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