Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
