<p>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 &gt; 2$, assuming paths are not required to be simple.  If you require paths to be simple and have $C&gt;2$, the problem is NP-hard, as <a href="https://cstheory.stackexchange.com/questions/41082/finding-shortest-path-while-maximizing-the-number-of-overlapping-edges/41093?noredirect=1#comment94504_41082">explained by Neal Young</a>.   So in the remainder of this answer I will assume that either $C \le 2$, or $C &gt;2$ and you allow non-simple paths.  I will describe the polynomial-time algorithm below.</p>

<p>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</p>

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

<p>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 <em>longest</em> path.  If $C \le 2$, iterate over all possible choices for $v,w$, and compute</p>

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

<p>If $C &gt; 2$, do the same but for the expression</p>

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

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

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-06-26T18:43:50.133Z
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$?
Hans
CC BY-SA 4.0
2018-06-27T00:17:41.867Z
@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.
D.W.
CC BY-SA 4.0
2018-06-27T18:37:18.600Z
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.
Hans
CC BY-SA 4.0
2018-06-27T21:10:22.337Z
@Hans, yikes!  No wonder you were thinking that.  Thanks for pointing that out. Fixed.
D.W.
CC BY-SA 4.0
2018-06-27T21:20:44.837Z
+1. Good now...
Hans
CC BY-SA 4.0
2018-06-26T15:39:51.040Z
2018-06-27T21:09:52.767Z
2018-06-27T21:09:52.767Z
D.W.
<p>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.</p>

<p>Consider the following variant:</p>

<p>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|$.</p>

<p>Has this problem been addressed before?</p>

CC BY-SA 4.0
2018-06-26T22:07:23.430Z
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.)
Neal Young
CC BY-SA 4.0
2018-06-27T01:04:55.617Z
This post is strangely similar to [this one](https://cstheory.stackexchange.com/questions/32024/finding-the-two-shortest-paths-while-minimizing-the-number-of-nearby-common-edge?rq=1).
Neal Young
<shortest-path>
Finding shortest path while maximizing the number of overlapping edges
Mojtaba
# Finding shortest path while maximizing the number of overlapping edges

(Asked by: username_0 on 2018-06-26)

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?

**Tags:** shortest-path
> **Comments:**
> **username_1**: 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.)  
> **username_1**: This post is strangely similar to [this one](https://cstheory.stackexchange.com/questions/32024/finding-the-two-shortest-paths-while-minimizing-the-number-of-nearby-common-edge?rq=1).  

---

## 1 answers

### Answer by username_2 on 2018-06-26. Score: 3 | Accepted answer

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](https://cstheory.stackexchange.com/questions/41082/finding-shortest-path-while-maximizing-the-number-of-overlapping-edges/41093?noredirect=1#comment94504_41082). 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.

> **Comments:**
> **username_3**: 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$?  
> **username_2**: @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.  
> **username_3**: 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.  
> **username_2**: @Hans, yikes!  No wonder you were thinking that.  Thanks for pointing that out. Fixed.  
> **username_3**: +1. Good now...  

---

