# the shorstest cycle containing two given points

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

• This is easily reducible to min-cost flow. – Chandra Chekuri Jan 23 at 14:33

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 for finding disjoint $$s$$$$t$$ shortest paths in a directed graph.