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?

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

Related Questions

Commutator estimates regarding pseudo-differential operators

0  Asked on December 15, 2020 by shaoyang-zhou

English translation of Borel-Serre Le theoreme de Riemann-Roch?:

1  Asked on December 15, 2020

Upper bound for an exponential sum involving characters of a finite field

1  Asked on December 14, 2020 by nahila

Euler function summation

0  Asked on December 13, 2020 by andrej-leko

A problem about an unramified prime in a Galois extension

1  Asked on December 9, 2020 by neothecomputer

Reference request: discretisation of probability measures on $mathbb R^d$

1  Asked on December 9, 2020 by mb2009

Smoothness of a variety implies homological smoothness of DbCoh

0  Asked on December 8, 2020 by dbcohsmoothness

Reference for matrices with all eigenvalues 1 or -1

1  Asked on December 7, 2020

Characterizations of groups whose general linear representations are all trivial

1  Asked on December 7, 2020 by qsh

Continuous time Markov chains and invariance principle

0  Asked on December 6, 2020 by sharpe

Continuity property for Čech cohomology

0  Asked on December 6, 2020 by xindaris

Reference request: superconformal algebras and representations

0  Asked on December 6, 2020 by winawer

Extending rational maps of nodal curves

1  Asked on December 5, 2020 by leo-herr

How large is the smallest ordinal larger than any “minimal ordinal parameter” for any pair of an Ordinal Turing Machine and a real?

1  Asked on December 4, 2020 by lyrically-wicked

Almost geodesic on non complete manifolds

1  Asked on December 4, 2020 by andrea-marino

With Khinchine’s inequality, prove Fourier basis is unconditional in $L^{p}[0,1]$ only for $p=2$

0  Asked on December 3, 2020 by eric-yan

Kähler manifolds deformation equivalent to projective manifolds

0  Asked on December 3, 2020 by user164740

Duality of eta product identities: a new idea?

2  Asked on December 1, 2020 by wolfgang

Is there a CAS that can solve a given system of equations in a finite group algebra $kG$?

2  Asked on December 1, 2020 by bernhard-boehmler