Fault-Tolerant ST-Diameter Oracles

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 Db 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) ≤ Db ≤ σ 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 Ω(n3/2) bits of space, regardless of the query time.