Bilò, Davide ;
Cohen, Sarel ;
Friedrich, Tobias ;
Schirneck, Martin
SpaceEfficient FaultTolerant Diameter Oracles
Abstract
We design fedge faulttolerant diameter oracles (fFDO, or simply FDO if f = 1). For a given directed or undirected and possibly edgeweighted graph G with n vertices and m edges and a positive integer f, we preprocess the graph and construct a data structure that, when queried with a set F of edges, where F ⩽ f, returns the diameter of GF. An fFDO has stretch σ ⩾ 1 if the returned value D^ satisfies diam(GF) ⩽ D^ ⩽ σ diam(GF).
For the case of a single edge failure (f = 1) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch (1+ε), constant query time, space O(m), and a combinatorial preprocessing time of Õ(mn + n^{1.5} √{Dm/ε}), where D is the diameter.
We present an FDO for directed graphs with the same stretch, query time, and space. It has a preprocessing time of Õ(mn + n²/ε), which is better for constant ε > 0. The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. With fast matrix multiplication, we achieve a preprocessing time of Õ(n^{2.5794} + n²/ε). We further prove an informationtheoretic lower bound showing that any FDO with stretch better than 3/2 requires Ω(m) bits of space. Thus, for constant 0 < ε < 3/2, our combinatorial (1+ε)approximate FDO is nearoptimal in all parameters.
In the case of multiple edge failures (f > 1) in undirected graphs with nonnegative edge weights, we give an fFDO with stretch (f+2), query time O(f²log²{n}), Õ(fn) space, and preprocessing time Õ(fm). We complement this with a lower bound excluding any finite stretch in o(fn) space.
Many realworld networks have polylogarithmic diameter. We show that for those graphs and up to f = o(log n/ log log n) failures one can swap approximation for query time and space. We present an exact combinatorial fFDO with preprocessing time mn^{1+o(1)}, query time n^o(1), and space n^{2+o(1)}. When using fast matrix multiplication instead, the preprocessing time can be improved to n^{ω+o(1)}, where ω < 2.373 is the matrix multiplication exponent.
BibTeX  Entry
@InProceedings{bilo_et_al:LIPIcs.MFCS.2021.18,
author = {Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin},
title = {{SpaceEfficient FaultTolerant Diameter Oracles}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {18:118:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14458},
URN = {urn:nbn:de:0030drops144581},
doi = {10.4230/LIPIcs.MFCS.2021.18},
annote = {Keywords: derandomization, diameter, distance sensitivity oracle, faulttolerant data structure, space lower bound}
}
18.08.2021
Keywords: 

derandomization, diameter, distance sensitivity oracle, faulttolerant data structure, space lower bound 
Seminar: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Issue date: 

2021 
Date of publication: 

18.08.2021 