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.

Bilò, D., D'Angelo, G., Gualà, L., Leucci, S., Proietti, G., Rossi, M. (2022). Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers. In Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.STACS.2022.12].

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

Gualà Luciano;
2022-01-01

Abstract

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.
39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022
fra
2022
Rilevanza internazionale
contributo
2022
Settore INF/01 - INFORMATICA
English
Edge-disjoint paths
Graph sparsification
Min-cost flow
Multipath spanners
Intervento a convegno
Bilò, D., D'Angelo, G., Gualà, L., Leucci, S., Proietti, G., Rossi, M. (2022). Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers. In Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.STACS.2022.12].
Bilò, D; D'Angelo, G; Gualà, L; Leucci, S; Proietti, G; Rossi, M
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/298917
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact