When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.13
URN: urn:nbn:de:0030-drops-85249
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8524/
 Go to the corresponding LIPIcs Volume Portal

### Efficient Oracles and Routing Schemes for Replacement Paths

 pdf-format:

### 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},