Bilò, Davide ;
D'Angelo, Gianlorenzo ;
Gualà, Luciano ;
Leucci, Stefano ;
Proietti, Guido ;
Rossi, Mirko
SingleSource Shortest pDisjoint Paths: Fast Computation and Sparse Preservers
Abstract
Let G be a directed graph with n vertices, m edges, and nonnegative 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 edgedisjoint 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 singlesource 2multipath preserver, i.e., a subgraph containing 2 edgedisjoint 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 singlesource pmultipath preserver with p(n1) edges. This size is optimal since the indegree of each nonroot vertex v must be at least p. Moreover, we design an algorithm that requires O(pn² (p + log n)) time to compute both p edgedisjoint paths of minimum total cost from the source to all other vertices and an optimalsize singlesource pmultipath preserver. The running time of our algorithm outperforms that of a natural approach that solves n1 singlepair instances using the wellknown 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 vertexdisjoint paths.
BibTeX  Entry
@InProceedings{bilo_et_al:LIPIcs.STACS.2022.12,
author = {Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko},
title = {{SingleSource Shortest pDisjoint Paths: Fast Computation and Sparse Preservers}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {12:112:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15822},
URN = {urn:nbn:de:0030drops158221},
doi = {10.4230/LIPIcs.STACS.2022.12},
annote = {Keywords: multipath spanners, graph sparsification, edgedisjoint paths, mincost flow}
}
09.03.2022
Keywords: 

multipath spanners, graph sparsification, edgedisjoint paths, mincost flow 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 