Bodwin, Greg and Grandoni, Fabrizio and Parter, Merav and Williams, Virginia Vassilevska (2017) Preserving Distances in Very Faulty Graphs. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland.
Full text not available from this repository.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 real-world networks are prone to failures, it makes sense to study fault-tolerant 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 worst-case size of a preserver for a single pair of nodes in the presence of f edge faults? There are no super-linear 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 sub-quadratic size single-pair preservers in unweighted (possibly directed) graphs for any fixed number f of faults. Our result indeed generalizes to the single-source case, and can be used to build new fault-tolerant additive spanners (for all pairs). • The size of the above single-pair preservers is O(n2−g(f)) for some positive function g, and grows to O(n2) 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(n2−ε) for ε > 0, then the additive error has to be Ω(ε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 Θ(n2) for f ≥ 2 in both directed and undirected graphs, while for f = 1 the size is Θ(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.
| Item Type: | Article in conference proceedings or Presentation at a conference (Paper) |
|---|---|
| Subjects: | Computer sciences > Computer science > Computational science foundations |
| Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 17 Jul 2023 11:15 |
| Last Modified: | 17 Jul 2023 11:19 |
| URI: | http://repository.supsi.ch/id/eprint/14339 |
Actions (login required)
 |
View Item |