3
$\begingroup$

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however the cost is considered to be the length of the paths minus a positive coefficient times the number of common edges in the two paths, i.e. cost is $|P_1|+|P_2|-C|P_1\cap P_2|$.

Has this problem been addressed before?

$\endgroup$
  • 1
    $\begingroup$ Do you require $P_1$ and $P_2$ to be simple? Are there any restrictions on $C$? (E.g. $C\le 2$?) Is your graph directed, undirected, a DAG? I ask because, e.g., in a general (undirected or directed) graph, if you require $P_1$ and $P_2$ to be simple, then the problem is NP-hard for any $C>2$. (Consider the instance where the two pairs of nodes are identical, then the problem with $C>2$ is equivalent to finding a longest path connecting the pair.) $\endgroup$ – Neal Young Jun 26 '18 at 22:07
  • $\begingroup$ This post is strangely similar to this one. $\endgroup$ – Neal Young Jun 27 '18 at 1:04
3
$\begingroup$

There is a polynomial-time algorithm for this problem in the case where $C \le 2$. There is also a polynomial-time algorithm when $C > 2$, assuming paths are not required to be simple. If you require paths to be simple and have $C>2$, the problem is NP-hard, as explained by Neal Young. So in the remainder of this answer I will assume that either $C \le 2$, or $C >2$ and you allow non-simple paths. I will describe the polynomial-time algorithm below.

First, note that in an optimal solution (wlog) the common part of the two paths must be contiguous, i.e., there is a single contiguous segment of $P_1$ that overlaps with $P_2$, and the rest does not. In particular, if we want shortest paths between $s_1 \leadsto t_1$ and $s_2 \leadsto t_2$, then there must exist some vertices $v,w$ such that $P_1$ has the form $s_1 \leadsto v \leadsto w \leadsto t_1$ and $P_2$ has the form $s_2 \leadsto v \leadsto w \leadsto t_2$ and the $s_1 \leadsto v$ and $w \leadsto t_1$ parts have no overlap with $P_2$, and the $v \leadsto w$ is common to both. The cost of this solution is then

$$|s_1 \leadsto v| + |w \leadsto t_1| + |s_2 \leadsto v| + |w \leadsto t_2| + (2-C) |v \leadsto w|.$$

So, compute all-pairs shortest paths and all-pairs longest paths; let $d(a,b)$ denote the distance (length of the shortest path) from $a$ to $b$, and $d^*(a,b)$ the length of the longest path. If $C \le 2$, iterate over all possible choices for $v,w$, and compute

$$d(s_1,v) + d(w,t_1) + d(s_2,v) + d(w,t_2) + (2-C) d(v,w).$$

If $C > 2$, do the same but for the expression

$$d(s_1,v) + d(w,t_1) + d(s_2,v) + d(w,t_2) + (2-C) d^*(v,w).$$

Keep the smallest value of this obtainable (i.e., the minimum over all $v,w$). That will be the solution to your problem. (We don't need to enforce the lack of overlap between, say, $s_1 \leadsto v$ and $s_2 \leadsto v$ in this calculation, because any overlap will only further lower the cost of the solution.)

The running time is something like $O(n^3)$, since the time is dominated by the time to compute all-pairs shortest paths. I make no claim that this is optimal.

My thanks to Neal Young for showing how to solve this when $C\le 2$, and for helping me make explicit my assumptions about whether paths are required to be simple or not.

$\endgroup$
  • $\begingroup$ For $C\ge2$, should you not have only one non-overlapping segment? Otherwise just replace every non-overlapping path with (the longer) one of the two paths. Also, your symbol $t_2$ is a bit confusing. Should it not be one the end points, namely, $t_1$? $\endgroup$ – Hans Jun 26 '18 at 18:43
  • $\begingroup$ @Hans, no. The input is two pairs $(s_1,t_1)$, $(s_2,t_2)$ of starting/ending positions for the two paths. You can't do the replacement you mention as that would change the starting position of the path. $\endgroup$ – D.W. Jun 27 '18 at 0:17
  • $\begingroup$ I misread the problem as having the same starting and ending ponts. Also, your typo "if we want shortest paths between $s_1 \leadsto t_1$ and $s_1 \leadsto t_2$" added to that confusion (since your second $s_1$ should be $s_2$). Anyway, my reasoning is still valid and is the reason of your "WLOG" statement of the common paths being contiguous. Also, it would be nice if you putting more explicit explanation of the $n^3$ complexity of the algorithm and show why this algorithm is optimal. $\endgroup$ – Hans Jun 27 '18 at 18:37
  • $\begingroup$ @Hans, yikes! No wonder you were thinking that. Thanks for pointing that out. Fixed. $\endgroup$ – D.W. Jun 27 '18 at 21:10
  • $\begingroup$ +1. Good now... $\endgroup$ – Hans Jun 27 '18 at 21:20

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.