License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.22
URN: urn:nbn:de:0030-drops-163633
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16363/
Bilò, Davide ;
Choudhary, Keerti ;
Cohen, Sarel ;
Friedrich, Tobias ;
Schirneck, Martin
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
Abstract
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs.
Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time.
BibTeX - Entry
@InProceedings{bilo_et_al:LIPIcs.ICALP.2022.22,
author = {Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin},
title = {{Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {22:1--22:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16363},
URN = {urn:nbn:de:0030-drops-163633},
doi = {10.4230/LIPIcs.ICALP.2022.22},
annote = {Keywords: derandomization, diameter, eccentricity, fault-tolerant data structure, sensitivity oracle, space lower bound}
}
Keywords: |
|
derandomization, diameter, eccentricity, fault-tolerant data structure, sensitivity oracle, space lower bound |
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
28.06.2022 |