Biḷ, 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 nvertex unweighted graph G=(V(G),E(G)), the replacement path pi_{Ge}(s,t) is a shortest st 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_{Ge}(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. faulttolerant 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{ST}) and query time of
O(\sqrt{ST}). At the expense of having quasipolynomial query time,
the size of the oracle can be improved to tilde{O}(nS+T\sqrt{Sn}), which is optimal for T = Omega(sqrt{nS}). 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 singlesource case, the above result is complemented by a lower bound conditioned on the SetIntersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings.
(2) FTP:
We show the construction of a pathreporting DSO of size tilde{O}(n^{4/3}(ST)^{1/3}) reporting pi_{Ge}(s,t) in O(pi_{Ge}(s,t)+(nST)^{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 polylogarithmic 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{Sn}) (up to inverse polylogarithmic factors).
(3) Routing and Labeling Schemes:
For the wellstudied singlesource setting, we present a novel routing scheme, that allows to route messages on pi_{Ge}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of polylogarithmic 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:113:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8524},
URN = {urn:nbn:de:0030drops85249},
doi = {10.4230/LIPIcs.STACS.2018.13},
annote = {Keywords: Fault tolerant, Shortest path, Oracle, Routing}
}
2018
Keywords: 

Fault tolerant, Shortest path, Oracle, Routing 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

2018 