2026-07-22T13:28:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15822 2024-03-06T10:56:16Z ddc:004 open_access

Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers Bilò, Davide D'Angelo, Gianlorenzo Gualà, Luciano Leucci, Stefano Proietti, Guido Rossi, Mirko multipath spanners graph sparsification edge-disjoint paths min-cost flow 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+nlog 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(pn² (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 Θ(m/(np)) and is asymptotically near optimal if p = O(1) and m = Θ(n²). Our results extend naturally to the case of p vertex-disjoint paths. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Gianlorenzo D'Angelo and Luciano Gualà and Stefano Leucci and Guido Proietti and Mirko Rossi 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.12 urn:nbn:de:0030-drops-158221 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.12 eng https://creativecommons.org/licenses/by/4.0/legalcode