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

  • 3
    $\begingroup$ This is easily reducible to min-cost flow. $\endgroup$ – Chandra Chekuri Jan 23 '20 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.

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.


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.