# 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

### The action of a subgroup of the torsion group of elliptic curves on integral points?

1  Asked on November 12, 2021 by user6671

### Data abstraction in set theory via Urelements

1  Asked on November 12, 2021 by steven-obua

### Closed form for the integral of a squared Legendre function

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

### Sufficient conditions for $mathrm{Der}_k(A)$ to be f.g. projective

1  Asked on November 12, 2021 by tobias-fritz

### Curvature collineation and the Killing identity

1  Asked on November 12, 2021 by spoilt-milk

### Random walk in a switching scenery

0  Asked on November 12, 2021

### Modern example of a reciprocity law and intuition behind it

0  Asked on November 12, 2021

### Hodge numbers rule out good reduction

1  Asked on November 12, 2021

### Positivity of $int_{-infty}^{infty} left{{2^{1/beta-1/2} over v}right}^{it} { Gamma{(it+1)/beta}over Gamma{(it+1)/2} }dt$

1  Asked on November 9, 2021 by vova

### Solving system of bilinear equations

1  Asked on November 9, 2021 by grok

### Invariant theory in universal algebra

0  Asked on November 9, 2021

### Motivic cohomology and resolution of singularities

0  Asked on November 9, 2021 by user161444

### Do roots of polynomial with coefficients in a CM field lie in a CM field?

0  Asked on November 9, 2021

### Exit time for Brownian motion with stochastic barriers

0  Asked on November 9, 2021 by as1

### Concavity of distance to the boundary of Riemannian manifold

0  Asked on November 9, 2021 by makt

### About functions primitive recursively definable using a $Sigma _ 1$ oracle

0  Asked on November 9, 2021 by mohsen-shahriari

### Infinite sum in power series ring

0  Asked on November 9, 2021

### Oldest abstract algebra book with exercises?

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