2026-07-24T06:08:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18076 2024-03-06T11:00:57Z ddc:004 open_access

Fault-Tolerant ST-Diameter Oracles Bilò, Davide Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Krogmann, Simon Schirneck, Martin diameter oracles distance sensitivity oracles space lower bounds fault-tolerant data structures We study the problem of estimating the ST-diameter of a graph that is subject to a bounded number of edge failures. An f-edge fault-tolerant ST-diameter oracle (f-FDO-ST) is a data structure that preprocesses a given graph G, two sets of vertices S,T, and positive integer f. When queried with a set F of at most f edges, the oracle returns an estimate D̂ of the ST-diameter diam(G-F,S,T), the maximum distance between vertices in S and T in G-F. The oracle has stretch σ ⩾ 1 if diam(G-F,S,T) ⩽ D̂ ⩽ σ diam(G-F,S,T). If S and T both contain all vertices, the data structure is called an f-edge fault-tolerant diameter oracle (f-FDO). An f-edge fault-tolerant distance sensitivity oracles (f-DSO) estimates the pairwise graph distances under up to f failures. We design new f-FDOs and f-FDO-STs by reducing their construction to that of all-pairs and single-source f-DSOs. We obtain several new tradeoffs between the size of the data structure, stretch guarantee, query and preprocessing times for diameter oracles by combining our black-box reductions with known results from the literature. We also provide an information-theoretic lower bound on the space requirement of approximate f-FDOs. We show that there exists a family of graphs for which any f-FDO with sensitivity f ⩾ 2 and stretch less than 5/3 requires Ω(n^{3/2}) bits of space, regardless of the query time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.24 urn:nbn:de:0030-drops-180762 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.24 eng https://creativecommons.org/licenses/by/4.0/legalcode