Fault-Tolerant ST-Diameter Oracles

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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> </mml:math> and $$t \in T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>T</mml:mi> </mml:mrow> </mml:math> . 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>D</mml:mi> <mml:mo>^</mml:mo> </mml:mover> </mml:math> of the ST -diameter in $$G\,{-}\,F$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mspace/> <mml:mo>-</mml:mo> <mml:mspace/> <mml:mi>F</mml:mi> </mml:mrow> </mml:math> . The oracle is said to have stretch $$\sigma \geqslant 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> if $${{\,\textrm{diam}\,}}(G{-}F,S,T) \leqslant \widehat{D} \leqslant \sigma \cdot {{\,\textrm{diam}\,}}(G{-}F,S,T)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>-</mml:mo> <mml:mi>F</mml:mi> <mml:mo>,</mml:mo> <mml:mi>S</mml:mi> <mml:mo>,</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>⩽</mml:mo> <mml:mover> <mml:mi>D</mml:mi> <mml:mo>^</mml:mo> </mml:mover> <mml:mo>⩽</mml:mo> <mml:mi>σ</mml:mi> <mml:mo>·</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>-</mml:mo> <mml:mi>F</mml:mi> <mml:mo>,</mml:mo> <mml:mi>S</mml:mi> <mml:mo>,</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> and stretch better than 5/3 requires $$\Omega (n^{3/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternativ