Abstract
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since realworld networks are prone to failures, it makes sense to study faulttolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain replacement paths around the faulted set. Unfortunately, the complexity of the interaction between replacement paths blows up significantly, even from 1 to 2 faults, and the structure of optimal preservers and spanners is poorly understood. In particular, no nontrivial bounds for preservers and additive spanners are known when the number of faults is bigger than 2.
Even the answer to the following innocent question is completely unknown: what is the worstcase size of a preserver for a single pair of nodes in the presence of f edge faults? There are no superlinear lower bounds, nor subquadratic upper bounds for f>2. In this paper we make substantial progress on this and other fundamental questions:
 We present the first truly subquadratic size faulttolerant singlepair preserver in unweighted (possibly directed) graphs: for any n node graph and any fixed number f of faults, O~(fn^{21/2^f}) size suffices. Our result also generalizes to the singlesource (all targets) case, and can be used to build new faulttolerant additive spanners (for all pairs).
 The size of the above singlepair preserver grows to O(n^2) for increasing f. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size O(n^{2eps}) for \eps>0, then the additive error has to be \Omega(eps f). This surprisingly matches known upper bounds in the literature.
 For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is Theta(n^2) for f > 1 in both directed and undirected graphs, while for f=1 the size is Theta(n) in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound.
Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.
BibTeX  Entry
@InProceedings{bodwin_et_al:LIPIcs:2017:7490,
author = {Greg Bodwin and Fabrizio Grandoni and Merav Parter and Virginia Vassilevska Williams},
title = {{Preserving Distances in Very Faulty Graphs}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {73:173:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7490},
URN = {urn:nbn:de:0030drops74906},
doi = {10.4230/LIPIcs.ICALP.2017.73},
annote = {Keywords: Fault Tolerance, shortest paths, replacement paths}
}
Keywords: 

Fault Tolerance, shortest paths, replacement paths 
Collection: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

07.07.2017 