Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers

Let G be a directed graph with n vertices, m edges, and non-negative edge costs. Given G, a fixed source vertex s, and a positive integer p, we consider the problem of computing, for each vertex t ≠ s, p edge-disjoint paths of minimum total cost from s to t in G. Suurballe and Tarjan [Networks, 1984] solved the above problem for p = 2 by designing a O(m + n log n) time algorithm which also computes a sparse single-source 2-multipath preserver, i.e., a subgraph containing 2 edge-disjoint paths of minimum total cost from s to every other vertex of G. The case p ≥ 3 was left as an open problem. We study the general problem (p ≥ 2) and prove that any graph admits a sparse single-source p-multipath preserver with p(n - 1) edges. This size is optimal since the in-degree of each non-root vertex v must be at least p. Moreover, we design an algorithm that requires O(pn2(p + log n)) time to compute both p edge-disjoint paths of minimum total cost from the source to all other vertices and an optimal-size single-source p-multipath preserver. The running time of our algorithm outperforms that of a natural approach that solves n - 1 single-pair instances using the well-known successive shortest paths algorithm by a factor of Θ(npm) and is asymptotically near optimal if p = O(1) and m = Θ(n2). Our results extend naturally to the case of p vertex-disjoint paths.