<p>Here is an answer to the first problem:</p>

<blockquote>
  <p><strong>Path with minimum weight gap:</strong> find an <span class="math-container">$s-t$</span> path, such that the difference between the largest  and smallest edge weights on the path is minimum.</p>
</blockquote>

<p>A paper from 1984 shows that whenever we can decide 
feasibility (does there exist a solution in the unweighted
case) for some combinatorial optimization problem in 
polynomial time, then we can also find in polynomial 
time a solution that minimizes the differenc between the 
largest and smallest cost coefficient (in the weighted case):</p>

<blockquote>
  <p>S. Martello, W.R. Pulleyblank, P. Toth, D. de Werra<br>
  Balanced optimization problems<br>
  Operations Research Letters 3, 1984, Pages 275-278</p>
</blockquote>

<p>This implies a polynomial time algorithm to your question.</p>

CC BY-SA 4.0
2019-09-14T01:32:20.733Z
This can also be done by a brute force search over all pairs of edges that could constitute the max and min, and their order/orientations.
Yonatan N
CC BY-SA 4.0
2019-09-13T06:11:05.870Z
2019-09-13T06:11:05.870Z
Gamow
<p><i>Path with minimum weight gap</i>: This can be solved in time <span class="math-container">$\tilde{O}(|E|^2)$</span>, where <span class="math-container">$|E|$</span> is the number of edges (assuming <span class="math-container">$|E|$</span> is at least linear in the number of vertices).  You can loop over the minimum weight, and do binary search (or efficient updates) over the maximum weight, and check connectivity.  I do not know whether this can be improved.</p>

<p><i>Path with minimum altitude</i> (in your terminology): This can be solved in time <span class="math-container">$\tilde{O}(|E|)$</span>.  You can compute distance (as in sum of 'step' sizes) to all edges analogously to ordinary weighted shortest path.  Note that repeated vertices cannot shorten a path.  To efficiently handle high degree vertices (as in avoiding time <span class="math-container">$|E|^2$</span>), you can split a vertex of degree <span class="math-container">$k$</span> into a path of <span class="math-container">$k-1$</span> vertices.</p>

<p><i>Path with minimum prime weight:</i>  If the weights are in binary, this should be NP complete:  Use weight 1 edges, except for the initial high-weight edge such that only a Hamilton path has prime weight (weight is the sum of edge weights).  (A caveat is that we have not proved that large-enough primes (even without minimum prime gaps) can be quickly found without randomness.)  Even for unary weights, I do not expect it to be in P.<br/>
<i>Minimum prime weight allowing self-intersections:</i> In P for unary weights.  If, in place of the set of primes, we used a set of random numbers <span class="math-container">$S$</span> with density <span class="math-container">$Θ(n/\log n)$</span>, then with probability 1, it is in <span class="math-container">$\mathrm{P}^S$</span> even for binary weights:  It suffices to keep track of polynomially many (dependent on <span class="math-container">$S$</span>) lowest path weights at each point.  However, with prime weights, we may have to diversify divisors of weight differences (instead of just keeping track of lowest weights), and it is unclear whether that is enough.</p>

<p><i>Smoothest path:</i>  NP complete.  If we allowed self-intersections, this would be solvable in time <span class="math-container">$\tilde{O}(|E|)$</span>, but for the version without self-intersections, here is a reduction from 3-SAT with <span class="math-container">$n$</span> variables.  Have vertices <span class="math-container">$s=v_0,v_1,...,t=v_n$</span>, plus a vertex for each clause.  For each variable <span class="math-container">$x_i$</span> (<span class="math-container">$i&lt;n$</span>), add a smooth path (using extra vertices if necessary) from <span class="math-container">$v_i$</span> to <span class="math-container">$v_{i+1}$</span> that passes through all clauses with positive occurrence of <span class="math-container">$x_i$</span>, and a similar path for clauses with <span class="math-container">$¬x_i$</span>.  Set the first and last edge weight of each path to 1 (or another constant), but otherwise choose weights such that no other paths are smooth.  Finally, duplicate all clause vertices and the adjoining edges; this way each clause can be visited at most twice, which suffices for 3-SAT.</p>

CC BY-SA 4.0
2019-09-19T02:39:16.833Z
I think, Smoothest path is in P, due to the following transformation. Let $v$ be a vertex of degree $d$. Replace $v$ with a clique of size $d$, such that each edge $e$ that was originally adjacent to $v$ now ends at a different vertex $v_e$ of the clique. If $e,f$ are two such original edges, then assign the weight $|w(e)-w(f)|$ to the  edge $(v_e,v_f)$ in the clique. Do this transformation for every vertex $v\neq s,t$, and assign 0 weight to the original graph edges. Then a minimum weight $s-t$ path in the new graph gives a smoothest path in the original, after undoing the transformation.
Andras Farago
CC BY-SA 4.0
2019-09-19T03:03:36.087Z
@AndrasFarago The problem with your argument is that some simple paths in the extended graph have repeated vertices in the original graph.  I like that the smoothest path problem looks deceptively simple.
Dmytro Taranovsky
CC BY-SA 4.0
2019-09-19T12:54:17.757Z
@ Dmytro Taranovsky It seems, you are right, it may indeed happen that after returning to the original graph we can get repeated vertices on the path (but no repeated edges). However, if each degree in the original graph is at most 3, then no repetition can happen. It means, the Smoothest Path problem is in P at least for graphs with maximum degree $\leq 3$.
Andras Farago
CC BY-SA 4.0
2019-09-19T14:12:53.740Z
Sorry, in the transformed graph we need to find a path with smallest maximum weight (which is also in P), rather than smallest total weight. The total weight would lead to a Path with Minimum Altitude (in graphs with max degree $\leq 3$, so that repeated vertices are excluded).
Andras Farago
CC BY-SA 4.0
2019-09-18T03:33:38.917Z
2019-09-18T03:33:38.917Z
Dmytro Taranovsky
<p>Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices <span class="math-container">$s,t$</span>. Below are some path problems that are all of the following form: find an <span class="math-container">$s-t$</span> path, such that some function of the edge weights on the path is minimum. In this sense they are all &quot;relatives&quot; of the shortest path problem; in the latter the function is simply the sum.</p>
<p><em>Note:</em> We are looking for simple paths, that is, without any repeated vertices. Since I did not find standard names for these problems in the literature, I named them myself.</p>
<blockquote>
<p><strong>Path with minimum weight gap:</strong> find an <span class="math-container">$s-t$</span> path, such that the difference between the largest  and smallest edge weights on the path is minimum.</p>
<p><strong>Smoothest path:</strong> find an <span class="math-container">$s-t$</span> path, such that the largest step size on the path is minimum, where a step size is the absolute value of the weight difference between two <em>consecutive</em> edges.</p>
<p><strong>Path with minimum altitude:</strong> Let us define the altitude of a path by the sum of the step sizes along the path (see the definition of step size above). Find an <span class="math-container">$s-t$</span> path with minimum altitude.</p>
<p><strong>Path with minimum prime weight:</strong> assuming that all edge weights are positive integers, find an <span class="math-container">$s-t$</span> path, such that its weight is a prime number. If there is such a path, find one with the smallest possible prime weight.</p>
</blockquote>
<p><strong>Question:</strong> what is known about these path problems? (And others that could be conceived in a similar spirit, applying a different function of the weights.) In general, is there any guidance that which functions of the edge weights can be minimized in polynomial time, and which are NP-hard?</p>
<p><strong>Note:</strong> it is interesting, for example, that while the sum of the weights is easy to minimize (it is the classical shortest path problem), but minimizing the closely related <em>average</em> of the weights on the path is NP-hard. (Assign weight 2 to all edges incident to <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, and weight 1 to all others. Then a min average weight path will be a longest <span class="math-container">$s-t$</span> path).</p>

<graph-theory><graph-algorithms><np-complete><polynomial-time>
"Relatives" of the shortest path problem
Andras Farago
# "Relatives" of the shortest path problem

(Asked by: username_0 on 2019-09-12)

Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such that some function of the edge weights on the path is minimum. In this sense they are all "relatives" of the shortest path problem; in the latter the function is simply the sum.

*Note:* We are looking for simple paths, that is, without any repeated vertices. Since I did not find standard names for these problems in the literature, I named them myself.

> **Path with minimum weight gap:** find an $s-t$ path, such that the difference between the largest and smallest edge weights on the path is minimum.
>
> **Smoothest path:** find an $s-t$ path, such that the largest step size on the path is minimum, where a step size is the absolute value of the weight difference between two *consecutive* edges.
>
> **Path with minimum altitude:** Let us define the altitude of a path by the sum of the step sizes along the path (see the definition of step size above). Find an $s-t$ path with minimum altitude.
>
> **Path with minimum prime weight:** assuming that all edge weights are positive integers, find an $s-t$ path, such that its weight is a prime number. If there is such a path, find one with the smallest possible prime weight.

**Question:** what is known about these path problems? (And others that could be conceived in a similar spirit, applying a different function of the weights.) In general, is there any guidance that which functions of the edge weights can be minimized in polynomial time, and which are NP-hard?

**Note:** it is interesting, for example, that while the sum of the weights is easy to minimize (it is the classical shortest path problem), but minimizing the closely related *average* of the weights on the path is NP-hard. (Assign weight 2 to all edges incident to $s$ and $t$, and weight 1 to all others. Then a min average weight path will be a longest $s-t$ path).

**Tags:** graph-theory, graph-algorithms, np-complete, polynomial-time

---

## 2 answers

### Answer by username_1 on 2019-09-13. Score: 8

Here is an answer to the first problem:

> **Path with minimum weight gap:** find an $s-t$ path, such that the difference between the largest and smallest edge weights on the path is minimum.

A paper from 1984 shows that whenever we can decide
feasibility (does there exist a solution in the unweighted
case) for some combinatorial optimization problem in
polynomial time, then we can also find in polynomial
time a solution that minimizes the differenc between the
largest and smallest cost coefficient (in the weighted case):

> S. Martello, W.R. Pulleyblank, P. Toth, D. de Werra  
> Balanced optimization problems  
> Operations Research Letters 3, 1984, Pages 275-278

This implies a polynomial time algorithm to your question.

> **Comments:**
> **username_2**: This can also be done by a brute force search over all pairs of edges that could constitute the max and min, and their order/orientations.  

---

### Answer by username_3 on 2019-09-18. Score: 4

*Path with minimum weight gap*: This can be solved in time $\tilde{O}(|E|^2)$, where $|E|$ is the number of edges (assuming $|E|$ is at least linear in the number of vertices). You can loop over the minimum weight, and do binary search (or efficient updates) over the maximum weight, and check connectivity. I do not know whether this can be improved.

*Path with minimum altitude* (in your terminology): This can be solved in time $\tilde{O}(|E|)$. You can compute distance (as in sum of 'step' sizes) to all edges analogously to ordinary weighted shortest path. Note that repeated vertices cannot shorten a path. To efficiently handle high degree vertices (as in avoiding time $|E|^2$), you can split a vertex of degree $k$ into a path of $k-1$ vertices.

*Path with minimum prime weight:* If the weights are in binary, this should be NP complete: Use weight 1 edges, except for the initial high-weight edge such that only a Hamilton path has prime weight (weight is the sum of edge weights). (A caveat is that we have not proved that large-enough primes (even without minimum prime gaps) can be quickly found without randomness.) Even for unary weights, I do not expect it to be in P.  
*Minimum prime weight allowing self-intersections:* In P for unary weights. If, in place of the set of primes, we used a set of random numbers $S$ with density $Θ(n/\log n)$, then with probability 1, it is in $\mathrm{P}^S$ even for binary weights: It suffices to keep track of polynomially many (dependent on $S$) lowest path weights at each point. However, with prime weights, we may have to diversify divisors of weight differences (instead of just keeping track of lowest weights), and it is unclear whether that is enough.

*Smoothest path:* NP complete. If we allowed self-intersections, this would be solvable in time $\tilde{O}(|E|)$, but for the version without self-intersections, here is a reduction from 3-SAT with $n$ variables. Have vertices $s=v\_0,v\_1,...,t=v\_n$, plus a vertex for each clause. For each variable $x\_i$ ($i), add a smooth path (using extra vertices if necessary) from $v\_i$ to $v\_{i+1}$ that passes through all clauses with positive occurrence of $x\_i$, and a similar path for clauses with $¬x\_i$. Set the first and last edge weight of each path to 1 (or another constant), but otherwise choose weights such that no other paths are smooth. Finally, duplicate all clause vertices and the adjoining edges; this way each clause can be visited at most twice, which suffices for 3-SAT.

> **Comments:**
> **username_0**: I think, Smoothest path is in P, due to the following transformation. Let $v$ be a vertex of degree $d$. Replace $v$ with a clique of size $d$, such that each edge $e$ that was originally adjacent to $v$ now ends at a different vertex $v_e$ of the clique. If $e,f$ are two such original edges, then assign the weight $|w(e)-w(f)|$ to the  edge $(v_e,v_f)$ in the clique. Do this transformation for every vertex $v\neq s,t$, and assign 0 weight to the original graph edges. Then a minimum weight $s-t$ path in the new graph gives a smoothest path in the original, after undoing the transformation.  
> **username_3**: @AndrasFarago The problem with your argument is that some simple paths in the extended graph have repeated vertices in the original graph.  I like that the smoothest path problem looks deceptively simple.  
> **username_0**: @ Dmytro Taranovsky It seems, you are right, it may indeed happen that after returning to the original graph we can get repeated vertices on the path (but no repeated edges). However, if each degree in the original graph is at most 3, then no repetition can happen. It means, the Smoothest Path problem is in P at least for graphs with maximum degree $\leq 3$.  
> **username_0**: Sorry, in the transformed graph we need to find a path with smallest maximum weight (which is also in P), rather than smallest total weight. The total weight would lead to a Path with Minimum Altitude (in graphs with max degree $\leq 3$, so that repeated vertices are excluded).  

---

