License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.13
URN: urn:nbn:de:0030-drops-85249
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8524/
Bilò, Davide ;
Choudhary, Keerti ;
Gualà, Luciano ;
Leucci, Stefano ;
Parter, Merav ;
Proietti, Guido
Efficient Oracles and Routing Schemes for Replacement Paths
Abstract
Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is a shortest s-t path that avoids e. In this paper we present several efficient constructions that, for every (s,t) \in S x T, where S, T \subseteq V(G), and every e \in E(G), maintain the collection of all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)).
More precisely, we provide the following results:
(1) DSO:
For every S,T \subseteq V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size tilde{O}(n\sqrt{|S||T|}) and query time of
O(\sqrt{|S||T|}). At the expense of having quasi-polynomial query time,
the size of the oracle can be improved to tilde{O}(n|S|+|T|\sqrt{|S|n}), which is optimal for |T| = Omega(sqrt{n|S|}). When |T| = Omega(n^frac{3}{4} |S|^frac{1}{4}), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings.
(2) FTP:
We show the construction of a path-reporting DSO of size tilde{O}(n^{4/3}(|S||T|)^{1/3}) reporting pi_{G-e}(s,t) in O(|pi_{G-e}(s,t)|+(n|S||T|)^{1/3}) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T=V(G). Our FTP improves over previous constructions when |T|=O(sqrt{|S|n}) (up to inverse poly-logarithmic factors).
(3) Routing and Labeling Schemes:
For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pi_{G-e}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.
BibTeX - Entry
@InProceedings{bil_et_al:LIPIcs:2018:8524,
author = {Davide Bil{\`o} and Keerti Choudhary and Luciano Gual{\`a} and Stefano Leucci and Merav Parter and Guido Proietti},
title = {{Efficient Oracles and Routing Schemes for Replacement Paths}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {13:1--13:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8524},
URN = {urn:nbn:de:0030-drops-85249},
doi = {10.4230/LIPIcs.STACS.2018.13},
annote = {Keywords: Fault tolerant, Shortest path, Oracle, Routing}
}
|
Keywords: |
|
Fault tolerant, Shortest path, Oracle, Routing |
|
Collection: |
|
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.02.2018 |
