Fault-Tolerant ST-Diameter Oracles
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck · Algorithmica · 2026
Abstract Given two vertex sets S and T in a graph, the ST -diameter is the maximum s - t -distance between vertices $$s \in S$$ s ∈ S and $$t \in T$$ t ∈ T . We study the problem of estimating the ST -diameter of graphs that are subject to a small number of transient edge failures. An f-edge fault-tolerant ST-diameter oracle ( f -FDO- ST ) is a data structure that preprocesses a graph G , sets S , T , and a positive integer f . When queried with a set F of at most f failing edges, the oracle returns an estimate $$\widehat{D}$$ D ^ of the ST -diameter in $$G\,{-}\,F$$ G - F . The oracle is said to have stretch $$\sigma \geqslant 1$$ σ ⩾ 1 if $${{\,\textrm{diam}\,}}(G{-}F,S,T) \leqslant \widehat{D} \leqslant \sigma \cdot {{\,\textrm{diam}\,}}(G{-}F,S,T)$$ diam ( G - F , S , T ) ⩽ D ^ ⩽ σ · diam ( G - F , S , T ) . We design new f -FDO- ST s by reducing their construction to that of all-pairs and single-source distance sensitivity oracles ( f -DSOs). These are data structures that estimate the pairwise graph distances, or respectively the distances from a distinguished source, under up to f failures. We obtain several new trade-offs between the size of the ST -diameter oracles, their stretch guarantees, query and preprocessing times by combining our black-box reductions with f -DSO results from the literature. We further provide a lower bound on the space requirement of approximate ST -diameter oracles. We prove that there exists a family of graphs for which any f -FDO- ST with sensitivity $$f \geqslant 2$$ f ⩾ 2 and stretch better than 5/3 requires $$\Omega (n^{3/2})$$ Ω ( n 3 / 2 )