10
$\begingroup$

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).

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yonatan N Sep 14 at 1:32
3
$\begingroup$

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<n$), 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andras Farago Sep 19 at 2:39
  • $\begingroup$ @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. $\endgroup$ – Dmytro Taranovsky Sep 19 at 3:03
  • $\begingroup$ @ 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$. $\endgroup$ – Andras Farago Sep 19 at 12:54
  • $\begingroup$ 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). $\endgroup$ – Andras Farago Sep 19 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.