<p>The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying <a href="https://en.wikipedia.org/wiki/Suurballe%27s_algorithm" rel="nofollow noreferrer">Suurballe's algorithm</a> for finding disjoint <span class="math-container">$s$</span>–<span class="math-container">$t$</span> shortest paths in a directed graph.</p>

<p>It doesn't quite work to turn your given undirected graph directed by replacing each undirected edge by two directed edges and to apply Suurballe to the resulting directed graph: you will get two paths that do not use the same directed edge, but they may share vertices or even use the same undirected edge (in opposite directions by the two paths).</p>

<p>Instead, first replace each undirected edge by two directed edges to form a directed graph. Then, in the resulting directed graph, split each vertex into two, one for the incoming adjacencies and one for the outgoing adjacencies, connected by an edge from incoming to outgoing. Finally, apply Suurballe to this graph. The result will be two directed paths that translate back to the two undirected graphs of minimum total edge length.</p>

CC BY-SA 4.0
2020-01-23T19:43:56.230Z
2020-01-23T19:43:56.230Z
David Eppstein
<p>I am given a edge-weighted (multi)graph <span class="math-container">$G$</span> and two of its vertices, <span class="math-container">$u, v\in V(G)$</span>. I want to find two edge-disjoint paths that connects <span class="math-container">$u$</span> and <span class="math-container">$v$</span> while minimizing the sum of the lengths of the paths. </p>

<p><em>what is the complexity of this problem ?</em></p>

<p>(If can reduce Hamiltonian Cycle to it if we ask for vertex-disjoint paths and allow negatives weights)</p>

<p><em>Anything known about approximation algorithms in general ? in planar graphs ?</em>  </p>

<p>(if we can cheat by an edge twice and paying it twice, then finding a shortest path gives a <span class="math-container">$2$</span>-approximation.)</p>

<p><em>More generally, what if now I ask for <span class="math-container">$k$</span> edge-disjoints paths between from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> ?</em></p>

<p>rq: this problem looks somehow related to subset TSP</p>

CC BY-SA 4.0
2020-01-23T14:33:06.260Z
This is easily reducible to min-cost flow.
Chandra Chekuri
<cc.complexity-theory><approximation-algorithms><approximation-hardness><planar-graphs>
the shorstest cycle containing two given points
Mathieu Mari
# the shorstest cycle containing two given points

(Asked by: username_0 on 2020-01-23)

I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the paths.

*what is the complexity of this problem ?*

(If can reduce Hamiltonian Cycle to it if we ask for vertex-disjoint paths and allow negatives weights)

*Anything known about approximation algorithms in general ? in planar graphs ?*

(if we can cheat by an edge twice and paying it twice, then finding a shortest path gives a $2$-approximation.)

*More generally, what if now I ask for $k$ edge-disjoints paths between from $u$ to $v$ ?*

rq: this problem looks somehow related to subset TSP

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness, planar-graphs

> **Comments:**
> **username_1**: This is easily reducible to min-cost flow.  

---

## 1 answers

### Answer by username_2 on 2020-01-23. Score: 3 | Accepted answer

The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying [Suurballe's algorithm](https://en.wikipedia.org/wiki/Suurballe%27s_algorithm) for finding disjoint $s$–$t$ shortest paths in a directed graph.

It doesn't quite work to turn your given undirected graph directed by replacing each undirected edge by two directed edges and to apply Suurballe to the resulting directed graph: you will get two paths that do not use the same directed edge, but they may share vertices or even use the same undirected edge (in opposite directions by the two paths).

Instead, first replace each undirected edge by two directed edges to form a directed graph. Then, in the resulting directed graph, split each vertex into two, one for the incoming adjacencies and one for the outgoing adjacencies, connected by an edge from incoming to outgoing. Finally, apply Suurballe to this graph. The result will be two directed paths that translate back to the two undirected graphs of minimum total edge length.


---

