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/
Go to the corresponding LIPIcs Volume Portal

Bilò, Davide ; Choudhary, Keerti ; Cohen, Sarel ; Friedrich, Tobias ; Schirneck, Martin

Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

pdf-format:
LIPIcs-ICALP-2022-22.pdf (0.8 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI