The Undirected Two Disjoint Shortest Paths Problem

Marinus Gottschau; Marcus Kaiser; Clara Waldmann

paper

The Undirected Two Disjoint Shortest Paths Problem

arXiv:1809.03820

Abstract

The $k$ disjoint shortest paths problem ( $k$ -DSPP) on a graph with $k$ source-sink pairs $(s_{i}, t_{i})$ asks for the existence of $k$ pairwise edge- or vertex-disjoint shortest $s_{i}$ - $t_{i}$ -paths. It is known to be NP-complete if $k$ is part of the input. Restricting to $2$ -DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial time algorithm based on dynamic programming for $2$ -DSPP on undirected graphs with non-negative edge lengths.

6 pages, 4 figures