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

0 Asked on December 15, 2020 by shaoyang-zhou

1 Asked on December 15, 2020

1 Asked on December 14, 2020 by nahila

2 Asked on December 10, 2020 by yada

1 Asked on December 9, 2020 by neothecomputer

ac commutative algebra algebraic number theory nt number theory ra rings and algebras

1 Asked on December 9, 2020 by mb2009

0 Asked on December 8, 2020 by dbcohsmoothness

ag algebraic geometry derived algebraic geometry derived categories homological algebra

1 Asked on December 7, 2020

1 Asked on December 7, 2020 by qsh

algebraic groups geometric group theory gr group theory linear algebra rt representation theory

0 Asked on December 6, 2020 by sharpe

0 Asked on December 6, 2020 by xindaris

at algebraic topology cohomology limits and colimits sheaf cohomology

0 Asked on December 6, 2020 by winawer

lie superalgebras mp mathematical physics reference request rt representation theory vertex algebras

1 Asked on December 5, 2020 by leo-herr

ag algebraic geometry algebraic curves birational geometry blow ups

1 Asked on December 4, 2020 by lyrically-wicked

1 Asked on December 4, 2020 by andrea-marino

calculus of variations connections differential topology geodesics transversality

0 Asked on December 3, 2020 by eric-yan

0 Asked on December 3, 2020 by user164740

ag algebraic geometry at algebraic topology complex geometry dg differential geometry gt geometric topology

2 Asked on December 1, 2020 by wolfgang

big picture co combinatorics modular forms special functions

2 Asked on December 1, 2020 by bernhard-boehmler

computer algebra finite groups gr group theory ra rings and algebras rt representation theory

Get help from others!

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?

Recent Answers

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

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