Department of Humanities and Social Sciences, University of Sassari,
<EMAIL_ADDRESS>This work was partially supported
by the Research Grant FBS2016_BILO, funded by “Fondazione di Sardegna” in
2016. Hasso Plattner Institute, University of Potsdam,
<EMAIL_ADDRESS>Hasso Plattner Institute, University of Potsdam,
<EMAIL_ADDRESS>Hasso Plattner Institute,
University of Potsdam<EMAIL_ADDRESS>Davide Bilò, Sarel
Cohen, Tobias Friedrich, and Martin Schirneck <ccs2012> <concept>
<concept_id>10003752.10003809.10003635.10010037</concept_id>
<concept_desc>Theory of computation Shortest paths</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10010031</concept_id> <concept_desc>Theory of
computation Data structures design and analysis</concept_desc>
<concept_significance>300</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10010031.10010035</concept_id>
<concept_desc>Theory of computation Cell probe models and lower
bounds</concept_desc> <concept_significance>300</concept_significance>
</concept> <concept> <concept_id>10003752.10010061.10010062</concept_id>
<concept_desc>Theory of computation Pseudorandomness and
derandomization</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>
[500]Theory of computation Shortest paths [300]Theory of computation Data
structures design and analysis [300]Theory of computation Cell probe models
and lower bounds [300]Theory of computation Pseudorandomness and
derandomization

# Space-Efficient Fault-Tolerant Diameter Oracles

Davide Bilò  Sarel Cohen  Tobias Friedrich  Martin Schirneck

###### Abstract

We design _$f$ -edge fault-tolerant diameter oracles_ ($f$-FDO, or simply FDO
if $f=1$). For a given directed or undirected and possibly edge-weighted graph
$G$ with $n$ vertices and $m$ edges and a positive integer $f$, we preprocess
the graph and construct a data structure that, when queried with a set $F$ of
edges, where $|F|\leqslant f$, returns the diameter of $G\,{-}\,F$. An $f$-FDO
has stretch $\sigma\geqslant 1$ if the returned value $\widehat{D}$ satisfies
$\operatorname{diam}(G\,{-}\,F)\leqslant\widehat{D}\leqslant\sigma\operatorname{diam}(G\,{-}\,F)$.

For the case of a single edge failure ($f=1$) in an unweighted directed graph,
there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch
$(1+\varepsilon)$, constant query time, space $O(m)$, and a combinatorial
preprocessing time of
$\widetilde{O}(mn+n^{1.5}\mathchoice{{\hbox{$\displaystyle\sqrt{Dm/\varepsilon\,}$}\lower
0.4pt\hbox{\vrule
height=7.5pt,depth=-6.00003pt}}}{{\hbox{$\textstyle\sqrt{Dm/\varepsilon\,}$}\lower
0.4pt\hbox{\vrule
height=7.5pt,depth=-6.00003pt}}}{{\hbox{$\scriptstyle\sqrt{Dm/\varepsilon\,}$}\lower
0.4pt\hbox{\vrule
height=5.25pt,depth=-4.20003pt}}}{{\hbox{$\scriptscriptstyle\sqrt{Dm/\varepsilon\,}$}\lower
0.4pt\hbox{\vrule height=3.75pt,depth=-3.00002pt}}})$, where $D$ is the
diameter.

We present an FDO for directed graphs with the same stretch, query time, and
space. It has a preprocessing time of $\widetilde{O}(mn+n^{2}/\varepsilon)$,
which is better for constant $\varepsilon>0$. The preprocessing time nearly
matches a conditional lower bound for combinatorial algorithms, also by
Henzinger et al. With fast matrix multiplication, we achieve a preprocessing
time of $\widetilde{O}(n^{2.5794}+n^{2}/\varepsilon)$. We further prove an
information-theoretic lower bound showing that any FDO with stretch better
than $3/2$ requires $\Omega(m)$ bits of space. Thus, for constant
$0<\varepsilon<3/2$, our combinatorial $(1+\varepsilon)$-approximate FDO is
near-optimal in all parameters.

In the case of multiple edge failures ($f>1$) in undirected graphs with non-
negative edge weights, we give an $f$-FDO with stretch $(f+2)$, query time
$O(f^{2}\log^{2}{n})$, $\widetilde{O}(fn)$ space, and preprocessing time
$\widetilde{O}(fm)$. We complement this with a lower bound excluding any
finite stretch in $o(fn)$ space.

Many real-world networks have polylogarithmic diameter. We show that for those
graphs and up to $f=o(\log n/\log\log n)$ failures one can swap approximation
for query time and space. We present an exact combinatorial $f$-FDO with
preprocessing time $mn^{1+o(1)}$, query time $n^{o(1)}$, and space
$n^{2+o(1)}$. When using fast matrix multiplication instead, the preprocessing
time can be improved to $n^{\omega+o(1)}$, where $\omega<2.373$ is the matrix
multiplication exponent.

###### keywords:

derandomization, diameter, distance sensitivity oracle, fault-tolerant data
structure, space lower bound

##  1 Introduction

The diameter is one of the most fundamental graph parameters. It plays a
particular significant role in the analysis of communication networks as the
time to transmit a message to all nodes is strongly related with the diameter.
Several lines of work have recently attacked the problem of computing the
diameter in different settings. For example, Choudhary and Gold [16]
constructed diameter spanners, which are subgraphs that approximately preserve
the diameter of the original graph, Ancona et al. [6] developed algorithms for
computing the diameter in dynamic scenarios and proved matching conditional
lower bounds, and Bonnet [10] proved that, for any constant $\varepsilon>0$,
computing a $(7/4-\varepsilon)$-approximation of the diameter of a sparse
graph $n$ vertices and $m=n^{1+o(1)}$ edges requires $m^{4/3-o(1)}$ time,
unless the Strong Exponential Time Hypothesis fails.

In this paper, we approach the diameter from the perspective of fault
tolerance. A communication network may be subject to a small number of
transient failures, and we want to quickly find out the new diameter without
recomputing it from scratch. Therefore, we study the problem of constructing
space-efficient data structures that can quickly report the diameter even if
up to $f$ edges fail in the graph. We refer to them as _$f$ -edge fault-
tolerant diameter oracles_ ($f$-FDO, or simply FDO if $f=1$). More precisely,
given an undirected or directed and possibly edge-weighted graph $G$ and a
positive integer $f$, we want to construct an $f$-FDO that, when queried on a
set $F$ of up to $f$ edges of $G$, returns a value $\widehat{D}$ that is
always at least as large the diameter of $G\,{-}\,F$, denoted by
$\operatorname{diam}(G\,{-}\,F)$. We say that an $f$-FDO has a _stretch_ of
$\sigma\geqslant 1$ (or that it is _$\sigma$ -approximate_) if the value
$\widehat{D}$ returned by the oracle additionally satisfies
$\operatorname{diam}(G\,{-}\,F)\leqslant\widehat{D}\leqslant\sigma\operatorname{diam}(G\,{-}\,F)$.

When designing $f$-FDOs one must find a good compromise between the following
parameters: the stretch, the time needed to query the oracle, the size of the
data structure, and the preprocessing time needed to build it. We focus
particularly on space-optimal solutions, while keeping the query and
preprocessing times low. For the case of a single edge failure in undirected
edge-weighted graphs, there are two folklore FDOs known. One reports the exact
diameter and has size $O(m)$, while the other takes $O(n)$ space, but
guarantees only a stretch of $2$. (more details are given in Section 2.1.) In
a sense they mark the extreme points of a spectrum. It is natural to ask
whether there are more trade-offs possible between the stretch and size of an
FDO. More precisely, we pose the following question.

Question 1 - space vs. approximation trade-off. What is the minimum achievable
size of an FDO for a given stretch $\sigma$? To answer the question, we prove
an information-theoretic lower bound. It shows that for undirected unweighted
graphs and every (even non-constant) $1\leqslant\sigma<3/2$, every
$\sigma$-approximate diameter oracle requires $\Omega(m)$ bits of space. The
space lower bound also holds for the harder case of directed graphs. The size
of the exact folklore FDO is thus optimal up to the size of a machine word.
Moreover, we prove that the stretch $2$ of the approximate FDO cannot be
improved on weighted graphs while keeping $O(n)$ space.

######  Theorem 1.1.

Any FDO with stretch $\sigma=\sigma(m)<3/2$ must take $\Omega(m)$ bits of
space on undirected graphs with $m$ edges. The bound increases to $\sigma<2$
if the graphs are edge-weighted.

When we focus our attention on the preprocessing time, the exact FDO can be
constructed in $\widetilde{O}(n^{3})$ time111 For a positive function
$g(n,m,f)$, we use $\widetilde{O}(g)$ to denote
$O(g\cdot\textsf{polylog}(n))$.  using the distance sensitivity oracle (DSO)
of Bernstein and Karger [8]. Henzinger et al. [30] proved an essentially
matching conditional lower bound for combinatorial222The term “combinatorial
algorithm” is not well-defined, and is often interpreted as not using any
matrix multiplication. Arguably, combinatorial algorithms can be considered
efficient in practice as the constants hidden in the matrix multiplication
bounds are rather high.  algorithms. They assumed that any combinatorial
algorithm requires $n^{3-o(1)}$ time to multiply two Boolean $n\times n$
matrices, known as the BMM conjecture. The restriction to combinatorial
algorithms is crucial as the task is reducible to integer matrices and one can
use fast matrix multiplication to solve it in $O(n^{\omega})$ time, where
$\omega<2.37286$ is the matrix multiplication exponent [2]. Under the BMM
conjecture, Henzinger et al. [30] showed that, for $0<\varepsilon<1/3$, any
combinatorial preprocessing algorithm requires $n^{3-o(1)}$ time to build an
FDO of stretch $(1+\varepsilon)$, even if we allow $O(n^{2-\delta})$ query
time for any constant $\delta>0$.

They match this bound with an FDO with stretch $(1+\varepsilon)$ and $O(1)$
query time that can be constructed in time
$\widetilde{O}(mn+n^{1.5}\mathchoice{{\hbox{$\displaystyle\sqrt{\operatorname{diam}(G)\cdot
m/\varepsilon\,}$}\lower 0.4pt\hbox{\vrule
height=7.5pt,depth=-6.00003pt}}}{{\hbox{$\textstyle\sqrt{\operatorname{diam}(G)\cdot
m/\varepsilon\,}$}\lower 0.4pt\hbox{\vrule
height=7.5pt,depth=-6.00003pt}}}{{\hbox{$\scriptstyle\sqrt{\operatorname{diam}(G)\cdot
m/\varepsilon\,}$}\lower 0.4pt\hbox{\vrule
height=5.25pt,depth=-4.20003pt}}}{{\hbox{$\scriptscriptstyle\sqrt{\operatorname{diam}(G)\cdot
m/\varepsilon\,}$}\lower 0.4pt\hbox{\vrule
height=3.75pt,depth=-3.00002pt}}})$. Their oracle also reports the radius and
vertex eccentricities in the presence of a single edge failure. Even on sparse
graphs with $m=\widetilde{O}(n)$ edges and constant diameter, the
preprocessing time is
$\widetilde{O}(n^{2.5}/\mathchoice{{\hbox{$\displaystyle\sqrt{\varepsilon\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\textstyle\sqrt{\varepsilon\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\scriptstyle\sqrt{\varepsilon\,}$}\lower
0.4pt\hbox{\vrule
height=3.01389pt,depth=-2.41113pt}}}{{\hbox{$\scriptscriptstyle\sqrt{\varepsilon\,}$}\lower
0.4pt\hbox{\vrule height=2.15277pt,depth=-1.72223pt}}})$. For constant
$\varepsilon>0$, this is by a factor $\textstyle\sqrt{n\,}$ larger than the
$\widetilde{O}(mn)$ time needed to build the DSO of Bernstein and Karger [8].
It is interesting whether one can close the gap.

Question 2 - fast preprocessing time. Does there exist a combinatorial
algorithm that constructs in $\widetilde{O}(mn)$ time an FDO with stretch
$(1+\varepsilon)$ and constant query time? In addition, can one bypass the
combinatorial lower bound by using fast matrix multiplication? We answer these
questions affirmatively for the diameter case with the following theorem. The
proof of the algebraic part uses the DSO presented very recently by Gu and Ren
[28].

######  Theorem 1.2.

For every unweighted directed graph and $\varepsilon>0$, there exists a
randomized combinatorial $(1+\varepsilon)$-approximate FDO that takes $O(m)$
space and has $\widetilde{O}(mn+n^{2}/\varepsilon)$ preprocessing time and
$O(1)$ query time. The returned values are correct w.h.p.333An event occurs
_with high probability_ (w.h.p.) if it has probability at least $1-n^{-c}$ for
some $c>0$.  Using fast matrix multiplication instead, one can construct the
FDO in time $\widetilde{O}(n^{2.5794}+n^{2}/\varepsilon)$.

Note that, for any constant $0<\varepsilon<1/3$, our combinatorial
$(1+\varepsilon)$-approximate combinatorial FDO from Theorem 1.2 is near-
optimal with respect to all parameters. The $\Theta(m)$ space is near-optimal
by Theorem 1.1, the query time is $\widetilde{O}(1)$, and the
$\widetilde{O}(mn)$ preprocessing time comes within sub-polynomial factors of
the conditional lower bound by Henzinger et al. [30]. Furthermore, when fast
matrix multiplication is permitted, our algebraic preprocessing algorithm is
even faster on dense graphs. However, our FDO is randomized.

Question 3 - derandomization. Can the construction of Theorem 1.2 be
derandomized in the same asymptotic running time? We answer this question
partially in that we derandomize the approximation part of our algorithm. When
combined with the DSO of Bernstein and Karger [8] this gives a deterministic
combinatorial FDO. For the derandomization, we adapt the framework of Alon,
Chechik, and Cohen [3]. We identify a set of $O(n^{3/2})$ critical paths one
needs to hit, and show how to compute them in $O(mn)$ time. It is then enough
to let the folklore greedy algorithm compute a hitting set in
$\widetilde{O}(n^{2})$ time.

It remains an open problem whether one can derandomize the algebraic approach,
whose randomization stems solely from the DSO by Gu and Ren [28].

######  Theorem 1.3.

For every unweighted directed graph and $\varepsilon>0$, there exists a
deterministic combinatorial $(1+\varepsilon)$-approximate FDO that takes
$O(m)$ space and has $\widetilde{O}(mn+n^{2}/\varepsilon)$ preprocessing time
and $O(1)$ query time.

Question 4 - space vs. approximation trade-off for multiple failures. Finally,
we consider the case of multiple edge failures and examine similar questions.
What is a the minimum size for an exact, respectively, approximate, diameter
oracle in the presence of up to $f$ edge failures? We again prove an
information-theoretic lower bound and show that for arbitrary finite stretch
$\sigma$, any $\sigma$-approximation diameter oracle requires $\Omega(fn)$
bits of space, at least if the oracle can be queried also with sets $F$ that
contain non-edges.

######  Theorem 1.4.

Suppose $f<n$. Any $f$-FDO with finite stretch that can be queried also for
non-edges must take $\Omega(fn)$ bits of space on graphs with $n$ vertices.

We develop an efficient $f$-FDO whose space requirement almost matches the
lower bound. Our result adapts and improves a construction by Bilò et al. [9].
Note that we use the $\widetilde{O}$-notation to suppress polylogarithmic
factors in $n$.

######  Theorem 1.5.

For every undirected graph with non-negative edge weights, there exists a
deterministic combinatorial $(f\,{+}\,2)$-approximate $f$-FDO that takes
$\widetilde{O}(fn)$ space and has $\widetilde{O}(fm)$ preprocessing time and
$\widetilde{O}(f^{2})$ query time.

Real-world networks are often described as having a small diameter, dubbed as
the “small world property” [35]. Many graph models used to analyze social and
communication networks have provable polylogarithmic guarantees on the
diameter, e.g. Chung-Lu graphs [17], hyperbolic random graphs [24], or the
preferential attachement model [31]. We show that on graphs with low diameter
one can swap approximation for query time even for multiple failures, while
still retaining efficient preprocessing time and a low space requirement To
achieve this, we combine fault-tolerant trees that where introduced by Chechik
et al. [13] with the random graphs of Weimann and Yuster [44].

######  Theorem 1.6.

Let $f$ be a positive integer and $\delta=\delta(n,m)>0$ a real number. For
every undirected unweighted graph with diameter at most
$n^{\delta/f}/(f{+}1)$, there exists a randomized combinatorial $f$-FDO that
takes $O(n^{2+\delta})$ space, has $O(2^{f})$ query time, and with high
probability $\widetilde{O}(fmn^{1+\delta}+f\hskip
1.00006ptn^{2+(2-1/f)\delta})$ preprocessing time. Using fast matrix
multiplication instead, one can construct the FDO w.h.p. in time
$\widetilde{O}(fn^{\omega+\delta}+f\hskip 1.00006ptn^{2+(2-1/f)\delta})$.

If the diameter is in fact polylogarithmic and the number of failures is
bounded by $f=o(\log n/\log\log n)$, we obtain the following corollary.

######  Corollary 1.7.

Let $f=o(\log n/\log\log n)$. For every undirected graph with polylogarithmic
diameter, there is an $f$-FDO that takes $n^{2+o(1)}$ space and has $n^{o(1)}$
query time. It can be preprocessed in time $mn^{1+o(1)}$, or algebraically in
time $n^{\omega+o(1)}$. If $f$ is constant, the preprocessing times are
$\widetilde{O}(mn)$, resp. $\widetilde{O}(n^{\omega})$, with
$\widetilde{O}(n^{2})$ space and $\widetilde{O}(1)$ query time.

###  1.1 Related Work

We briefly review previous work on distance sensitivity oracles and diameter
computation.

Distance sensitivity oracles. Distance oracles for all-pairs distances were
introduced in a seminal paper by Thorup and Zwick [43]. Demetrescu et al. [19]
extended the notion of distance oracles to the fault-tolerant setting in which
either an edge or a vertex of a graph can fail (i.e., distance sensitivity
oracles or DSOs). They showed that it is possible to preprocess a directed
weighted graph in $\widetilde{O}(mn^{2})$ time to compute a data-structure of
size $O(n^{2}\log n)$ capable of answering distance queries in constant time.
Bernstein and Karger [8] improved the preprocessing time to
$\widetilde{O}(mn)$ and Duan and Zhang [23] reduced the space to $O(n^{2})$,
which is asymptotically optimal.

Duan and Pettie [22] considered the more involved case of two failures and
presented an oracle with $O(n^{2}\log^{3}n)$ size, $O(\log n)$ query time and
polynomial construction time. Chechik et al. [13] presented a DSO of size
$O(n^{2+o(1)})$ that supports up to $o(\log n/\log\log n)$ edge failures and
guarantees a stretch of $(1+\epsilon)$, for every constant $\epsilon>0$. The
approach has been recently extended to also handle vertex failures by Duan,
Gu, and Ren [21].

The construction of DSOs have also been considered in the approximate regime
[13]. Algebraic algorithms are known to improve the preprocessing times, if
one is willing to employ fast matrix multiplication (for e.g., see [28, 12]
and the references therein).

Diameter computation. The fastest known combinatorial algorithms (up to
polylogarithmic factor) for both solving the all-pairs shortest paths (APSP)
problem and the diameter problem, are the trivial ones with
$\widetilde{O}(mn)$ running time. There is extensive research on developing
faster approximate APSP algorithms [7, 18, 33], as well as faster
approximation algorithms for the diameter [14, 41]. For special classes of
graphs, for example planar graphs, efficient exact algorithms for computing
the diameter are known [25].

##  2 Preliminaries

We let $G=(V,E)$ denote the (possibly directed) base graph on $n$ vertices and
$m$ edges. We tacitly assume that $G$ is (strongly) connected, i.e.,
$m=\Omega(n)$. For a graph $H$, we denote by $V(H)$ the set of its vertices,
and by $E(H)$ its edges. The _(closed) neighborhood_ of a vertex $v\in V(H)$
is the set $N[v]=\\{u\in V(H)\mid\\{v,u\\}\in E(H)\\}\cup\\{v\\}$. Let $P$ be
a path in $H$, its _length_ $|P|$ is the number of its edges. For any two
vertices $x,y\in V(P)$, $P[x..y]$ is the subpath of $P$ from $x$ to $y$. For
$s,t\in V(H)$, the _distance_ $d_{H}(s,t)$ is the minimum length of an
$s$-$t$-paths in $H$; if $s$ and $t$ are disconnected, we set
$d_{H}(s,t)=+\infty$. We drop the subscript when talking about the base graph
$G$. The _eccentricity_ of $s$ is $\operatorname{ecc}(s,H)=\max_{t\in
V(H)}d_{H}(s,t)$ and the _diameter_ is $\operatorname{diam}(H)=\max_{s\in
V(H)}\operatorname{ecc}(s,H)$. Any graph distance can be stored in a single
machine word on $O(\log n)$ bits. Unless explicitly stated otherwise, we
measure the space complexity in the number of words. For a collection
$F\subseteq\binom{V(H)}{2}$ of 2-sets of vertices (edges or non-edges), let
$H-F$ be the graph obtained from $H$ by removing all edges in $F$ (graph $H$
is not altered if $F\cap E(H)=\emptyset$). A _replacement path_ $P_{H}(s,t,F)$
is a shortest path from $s$ to $t$ in $H-F$. Its length
$d_{H}(s,t,F)=|P_{H}(s,t,F)|$ is the _replacement distance_. The _fault-
tolerant diameter_ of $H$ with respect to $F$ is the diameter of $H\,{-}\,F$.

For a positive integer $f$, an _$f$ -fault-tolerant diameter oracle_ ($f$-FDO)
for the graph $G$ is a data structure that reports, upon query $F$ with
$|F|\leqslant f$, the value $\operatorname{diam}(G\,{-}\,F)$. For any
$\sigma=\sigma(n,m,f)\geqslant 1$, such an oracle is $\sigma$_-approximate_ ,
or has _stretch_ $\sigma$, if it answers a query $F$ with a value
$\widehat{D}$ such that
$\operatorname{diam}(G\,{-}\,F)\leqslant\widehat{D}\leqslant\sigma\cdot\operatorname{diam}(G\,{-}\,F)$.
In case of a single failure, we write FDO for 1-FDO and abbreviate $F=\\{e\\}$
to $e$. An _$f$ -distance sensitivity oracle_ ($f$-DSO) reports, upon query
$(s,t,F)$ with $|F|\leqslant f$, the replacement distance $d(s,t,F)$.

###  2.1 (Mostly) Known FDOs for Single Edge Failures

The first folklore FDO handles single edge failures in unweighted (directed or
undirected) graphs. It has also been observed in [30]. The DSO of Bernstein
and Karger [8] constructible in $\widetilde{O}(mn)$ time and is able to report
in constant time the exact distance of any pair of vertices in the presence of
a single edge failure. With this one can construct the FDO by explicitly
computing all the eccentricities $\operatorname{ecc}(v,G-e)$, for every vertex
$v$ and every edge $e$ of $G$, in $O(n^{3})$ time. For a fixed vertex $v$, the
$m$ values $\operatorname{ecc}(v,G\,{-}\,e)$ can be obtained in $O(n^{2})$
time as follows. First compute a shortest paths tree $T_{v}$ of $G$ rooted at
$v$. For each edge $e$ that is not in $T_{v}$, we have that
$\operatorname{ecc}(v,G\,{-}\,e)=\operatorname{ecc}(v,G)$. For the tree-edges
$e$ in $T_{v}$, we use the DSO to compute $\operatorname{ecc}(v,G\,{-}\,e)$
which is the maximum distance from $v$ to any other vertex in $G\,{-}\,e$.
Therefore, $\operatorname{ecc}(v,G\,{-}\,e)$ can be computed by performing
$n-1$ queries, as there are $n-1$ edges in $T_{v}$, we need $O(n^{2})$ time.
The fault-tolerant diameter $\operatorname{diam}(G-e)$ is the maximum of the
$\operatorname{ecc}(v,G-e)$, it can be stored in $O(m)$ space with one entry
for each edge $e$.

The second folklore FDO can only be used for undirected edge-weighted graphs.
The FDO has stretch $2$ and uses the fact that the diameter of the graph is
intimately related to the eccentricity of _any_ vertex. For an arbitrary $v$,
we have that $\operatorname{ecc}(v,G)\leqslant\operatorname{diam}(G)\leqslant
2\operatorname{ecc}(v,G)$ as, by the triangle inequality, we can bound the
distance between any two vertices $u,u^{\prime}\in V$ by
$d_{G}(u,u^{\prime})\leqslant d_{G}(u,v)+d_{G}(v,u^{\prime})\leqslant
2\operatorname{ecc}(v,G)$. The FDO again computes a shortest paths tree $T$
rooted at a fixed source $v$ and stores an array of length $n-1$,
corresponding to the edges of $T$. For every such edge $e$, one computes and
stores $2\operatorname{ecc}(s,G-e)$. When queried with edge $e$, the FDO
returns the stored value or, if $e$ is not in the tree, the value
$2\operatorname{ecc}(s,G)$. The size of this FDO is $O(n)$.

A maybe lesser-known way of building FDOs is via spanners. For any $\sigma>0$,
we say that a subgraph $H$ of $G$ is a _spanner_ of stretch $\sigma$ if, for
every two vertices $s,t$ of $G$, we have $d_{H}(s,t)\leqslant\sigma
d_{G}(s,t)$. For every positive integer $k$, it is known how to construct a
spanner $H$ of $G$ such that (a) $H$ has a stretch of $2k-1$ and (b) the size
of $H$ is $O(n^{1+1/k})$ [5]. Observe that for every edge $e=\\{u,v\\}$ that
is in $G$ but not in $H$, we have $d(u,v,e)\leqslant 2k-1$. We now describe
how spanners can be used to construct another easy oracle for undirected
unweighted graphs whose stretch guarantee depends on both $k$ and the inverse
of $\operatorname{diam}(G)$. This implies that the oracle already performs
quite well for large-diameter graphs.

We construct such a spanner oracle with parameter $k$ by first computing a
spanner that satisfies (a) and (b). Then, we associate the value
$\operatorname{diam}(G-e)$ to each edge $e$ in the spanner $H$ and build a
dictionary in which we store information about the edges of the spanner
together with the corresponding associated values. Consider a query of edge
$e$. If $e\in E(H)$ the we return the value associated with $e$; otherwise, we
return $\operatorname{diam}(G)+2(k-1)$. The proof of the next lemma is
deferred to Appendix A.

######  Lemma 2.1.

For every positive integer $k$, the spanner oracle with parameter $k$ has
$O(n^{1+1/k})$ size, a constant query time, and a stretch of
$1+2(k-1)/\operatorname{diam}(G)$.

The result of Lemma 2.1 already implies the existence of sparse FDOs of $o(m)$
size and of stretch $\sigma<3/2$ for sufficiently dense graphs with diameter
strictly larger than 4. This does not contradict the lower bound of Theorem
1.1, but allows us to conclude that strong lower bounds on the size of FDOs
for unweighted undirected graphs can only hold when the diameter of the input
graph is bounded by a small constant.

##  3 Single Edge Failures

First, we treat single edge failures, $f=1$. In this section, we assume the
base graph $G$ to be directed and present an $(1+\varepsilon)$-approximate
fault-tolerant diameter oracle with space $O(m)$ and $O(1)$ query time. We
give two variants, one is deterministic and combinatorial, the other
randomized and algebraic. We then show that the space requirement is optimal
up to the size of the machine word.

###  3.1 An $(1+\varepsilon)$-approximate FDO for Single Failures

We construct here the approximate FDO, thereby proving Theorem 1.2. Suppose we
know for each $s,t\in V$ some shortest path $P(s,t)$ in $G$ and additionally
have access to a distance sensitivity oracle that, for any edge $e$, reports
in constant time the replacement distances $d(s,t,e)$ whenever needed.
Clearly, $d(s,t,e)$ differs from the original graph distance only if $e$ is on
$P(s,t)$. To determine the diameters of _all_ the graphs $G\,{-}\,e$, it is
thus enough to query the DSO only for the edges on the shortest paths, which
can be done in time $O(n^{2}\cdot\operatorname{diam}(G))$. We use
approximation to avoid the cubic running time in case of a large diameter. For
this, we randomly sample a small set $B$ of so-called _pivots_ and prove that
it is enough to compute the replacement distances only between pairs from
$B\times V$, instead of all pairs of vertices. Subsequently, we derandomize
the pivot selection.

We fill in the details starting with the APSP computation in $G$ and the
preprocessing of the DSO. The combinatorial version uses a breath-first search
from every vertex and the DSO of Bernstein and Karger [8], taking total time
$\widetilde{O}(mn)$. Alternatively, compute APSP algebraically and use the
randomized DSO by Gu and Ren [28].444 The DSO by Gu and Ren [28] is not path-
reporting; if it were, we would not have to compute APSP. The fastest path-
reporting algebraic DSO was given by Ren [39, 40] and can be constructed in
time $O(n^{2.7233})$ on directed graphs, respectively in time $O(n^{2.6865})$
on undirected graphs.  APSP is computable in time $O(n^{2.575})$ on unweighted
directed graphs with a variant of Zwick’s algorithm [45, Corollary 4.5], this
is in turn dominated by the $O(n^{2.5794})$ preprocessing time of the DSO
[28]. After these computation, the distances $d(s,t)$, shortest paths $P(s,t)$
in $G$, and the replacement distances $d(s,t,e)$ are available to us (w.h.p.,
in the randomized case) with a constant query time per distance/path edge.

From here on out, the process for both variants is the same. Our fault-
tolerant diameter oracle also allows non-edges to be queried, for which we
return the original diameter $\operatorname{diam}(G)$. To account for this, we
store all edges in a static dictionary of size $O(m)$ that allows for worst-
case constant look-up times after an $\widetilde{O}(m)$ preprocessing [4,
29].555The weak non-uniformity mentioned in [29], i.e., the need of compile-
time constants depending on the word size, only holds if this size is
$\omega(\log n)$, which is not the case for us.

Now fix a parameter $\varepsilon>0$ for the approximation, possibly even
depending on $m,n$. We initialize an array $D$ indexed by the edges of $G$,
all its cells hold the value $\operatorname{diam}(G)$. Assume first that
$\varepsilon\cdot\operatorname{diam}(G)=O(\log n)$. For any two vertices $s,t$
and edge $e$ on the shortest path $P(s,t)$, we update $D[e]$ to the maximum of
the previous value and $d(s,t,e)$. This takes
$O(n^{2}\operatorname{diam}(G))=\widetilde{O}(n^{2}/\varepsilon)$ time. After
all updates, the entry $D[e]$ stores the _exact_ fault-tolerant diameter
$\operatorname{diam}(G\,{-}\,e)$ (possibly w.h.p.). For
$\varepsilon\cdot\operatorname{diam}(G)=\omega(\log n)$, we first give a
randomized $(1{+}\varepsilon)$-approximation and later derandomize it in
Section 3.2. This yields the deterministic combinatorial algorithm of Theorem
1.3. The remaining use of randomness in the algebraic variant is due to the
DSO by Gu and Ren [28].

To guard for the case that the failure of $e$ disconnects the graph, we
compute all _strong bridges_ of $G$, that is, edges whose removal increases
the number of strongly connected components, in time $O(m)$ with the algorithm
by Italiano, Laura, and Santaroni [32]. For each strong bridge $e$, we set
$D[e]=\infty$. To compute the other entries, we construct the set $B\subseteq
V$ of pivots by randomly sampling every vertex independently with probability
$C(\log n)/(\varepsilon\operatorname{diam}(G))$ for a sufficiently large
constant $C>0$. A simple calculation using Chernoff bounds shows that
$|B|=\widetilde{O}(n/(\varepsilon\operatorname{diam}(G)))$ w.h.p. Moreover,
with high probability for all $s,t\in V$ and $e\in E$ such that
$\varepsilon\operatorname{diam}(G)<d(s,t,e)<\infty$, there exists a
replacement path from $s$ to $t$ that avoids $e$ and additionally contains a
pivot from $B$. See [27, 42] for details. We update the entries of $D$ in the
same fashion as above, but now only use the (directed) distance $d(x,t,e)$ for
all pivots $x\in B$ and vertices $t\in V$. In the end, we add
$\varepsilon\operatorname{diam}(G)$ to the value in $D[e]$. The array $D$ is
computable in time $O(m+n\hskip
1.00006pt|B|\operatorname{diam}(G))=\widetilde{O}(n^{2}/\varepsilon)$.

We verify that $D[e]$ is an $(1{+}\varepsilon)$-approximation of the fault-
tolerant diameter $\operatorname{diam}(G\,{-}\,e)$.

######  Lemma 3.1.

We have $\operatorname{diam}(G\,{-}\,e)\leqslant
D[e]\leqslant(1{+}\varepsilon)\operatorname{diam}(G\,{-}\,e)$ w.h.p.

######  Proof 3.2.

We can assume that $G\,{-}\,e$ is strongly connected as otherwise
$D[e]=\infty=\operatorname{diam}(G\,{-}\,e)$. The upper bound follows from
$D[e]=\max_{x\in B,t\in
V}d(x,t,e)+\varepsilon\operatorname{diam}(G)\leqslant(1{+}\varepsilon)\operatorname{diam}(G\,{-}\,e)$.

The main part consists of showing the lower bound
$D[e]\geqslant\operatorname{diam}(G\,{-}\,e)$. The idea is to prove the
existence of a pivot $x\in B$ and vertex $t\in V$ whose replacement distance
underestimates the fault-tolerant diameter by at most an additive term
$\varepsilon\operatorname{diam}(G)$, which we offset when computing $D[e]$. If
$\operatorname{diam}(G\,{-}\,e)\leqslant\varepsilon\operatorname{diam}(G)$
(which can only happen for $\varepsilon\geqslant 1$), the lower bound holds
vacuously as we have $D[e]\geqslant\varepsilon\operatorname{diam}(G)$.

Let thus vertices $s,t\in V$ be such that
$d(s,t,e)=\operatorname{diam}(G\,{-}\,e)>\varepsilon\operatorname{diam}(G)$.
Since $G\,{-}\,e$ is strongly connected the diameter is finite and realized by
some replacement path $P(s,t,e)$. In particular, we have
$|P(s,t,e)|>\varepsilon\operatorname{diam}(G)$. Let $y$ be the unique vertex
on $P(s,t,e)$ with $d(s,y,e)=\varepsilon\operatorname{diam}(G)$. Recall that
w.h.p. the set $B$ hits _some_ shortest path $P^{\prime}$ from $s$ to $y$ that
avoids $e$. The path $P^{\prime}$ is not necessarily equal to the subpath
$P(s,t,e)[s..y]$, but they have the same length $d(s,y,e)$. Substituting
$P^{\prime}$ for $P(s,t,e)[s..y]$ therefore guarantees a replacement path from
$s$ to $t$ that (w.h.p.) has a pivot $x\in B$ on its prefix of length
$\varepsilon\operatorname{diam}(G)$. For notational convenience, we use
$P(s,t,e)$ to also denote this particular path.

The replacement distance from pivot $x$ to target $t$ satisfies
$d(x,t,e)=|P(s,t,e)[x..t]|=|P(s,t,e)|-|P(s,t,e)[s..x]|\geqslant
d(s,t,e)-\varepsilon\operatorname{diam}(G)$. The entry $D[e]$ is also updated
using the pivot $x$, whence $D[e]\geqslant
d(x,t,e)+\varepsilon\operatorname{diam}(G)\geqslant
d(s,t,e)=\operatorname{diam}(G\,{-}\,e)$.

###  3.2 Derandomization

For the randomized combinatorial FDO, we had a preprocessing time of
$\widetilde{O}(mn+n^{2}/\varepsilon)$. The underlying APSP computation and the
DSO are deterministic. We now derandomize the approximation part in the same
asymptotic running time, proving Theorem 1.3. In 3.1, we used that the set $B$
intersects at least one long replacement path from $s$ to $t$ exactly. We
argue that it is in fact enough to hit the set of all vertices with distance
at most $\varepsilon\operatorname{diam}(G)$ from $s$ in each strongly
connected $G\,{-}\,e$. The pivot $x$ does not need to be on any replacement
path. The only assertion of 3.1 that is possibly in doubt is the lower bound
$D[e]\geqslant\operatorname{diam}(G\,{-}\,e)$. Let again $s$ and $t$ be such
that $d(s,t,e)=\operatorname{diam}(G\,{-}\,e)$ and let $x\in B$ be a pivot
with $d(s,x,e)=d_{G\,{-}\,e}(s,x)\leqslant\varepsilon\operatorname{diam}(G)$.
Whenever $G\,{-}\,e$ is strongly connected, a replacement path $P(x,t,e)$
exists and, by the triangle inequality, we have $d(x,t,e)\geqslant
d(s,t,e)-d(s,x,e)\geqslant d(s,t,e)-\varepsilon\operatorname{diam}(G)$. The
claim follows.

For the derandomization, we adopt the framework of Alon, Chechik and Cohen
[3]. This involves efficiently finding a small set of critical paths such that
hitting them ensures to hit each $(\varepsilon\operatorname{diam}(G))$-ball in
the strongly connected $G\,{-}\,e$. If the critical paths are both short
enough and few in numbers, it is then enough to compute the hitting set via
the folklore greedy algorithm. In [3], it was sufficient to give a single set
of critical paths. We generalize this to multiple sets, where the later-
defined sets depend on the paths in the former.

Set
$\ell=\min\\{\varepsilon\operatorname{diam}(G),\mathchoice{{\hbox{$\displaystyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\textstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\scriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=3.01389pt,depth=-2.41113pt}}}{{\hbox{$\scriptscriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule height=2.15277pt,depth=-1.72223pt}}}\\}$ and let $r$ be an
arbitrary vertex in $G$. We compute the in-tree $T_{\text{in}}(r)$, containing
the shortest paths in $G$ leading to $r$, with breath-first search. In the set
$\mathcal{P}$, we collect, for each vertex $s$ with $d(s,r)>\ell$, the path of
$T_{\text{in}}(r)$ starting in $s$ and having length $\ell$. Let
$P\in\mathcal{P}$ be a path with start vertex $s$ and let $e\in E(P)$ be such
that it is not a strong bridge. We compute the in-tree $T_{\text{in},e}(r)$ in
$G\,{-}\,e$ rooted in $r$. Note that $s$ has distance $d(s,r,e)\geqslant
d(s,r)>\ell$ from the root in the tree. We add the corresponding path to the
set $\mathcal{P}_{e}$. The original in-tree $T_{\text{in}}(r)$ contains only
$n-1$ edges, so all trees can be computed in total time666For a single source,
there are _randomized_ algorithms known that compute the trees faster [11, 15,
26].  $O(mn)$. Moreover, there are at most $\ell+1$ paths with starting vertex
$s$. In total, we thus have $O(n\ell)$ paths each of length $\ell$. A greedy
algorithm computes a hitting set $B$ for all paths in the $\mathcal{P}$ and
$\mathcal{P}_{e}$. It iteratively selects the vertex that is contained in the
most yet unhit paths, it terminates in time
$\widetilde{O}(n\ell^{2})=\widetilde{O}(n^{2})$ and produces a set of
$|B|=\widetilde{O}(n/\ell)=\widetilde{O}(n/(\varepsilon\operatorname{diam}(G))$
pivots, see [3, 34]. We used the definition
$\ell=\min\\{\varepsilon\operatorname{diam}(G),\mathchoice{{\hbox{$\displaystyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\textstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=4.30554pt,depth=-3.44446pt}}}{{\hbox{$\scriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule
height=3.01389pt,depth=-2.41113pt}}}{{\hbox{$\scriptscriptstyle\sqrt{n\,}$}\lower
0.4pt\hbox{\vrule height=2.15277pt,depth=-1.72223pt}}}\\}$ for both estimates.
Finally, we add the root $r$ to the set $B$ to cover all paths in the trees
that are shorter than $\ell$.

######  Lemma 3.3.

For each vertex $s\in V$ and edge $e$ such that $G\,{-}\,e$ is strongly
connected, there exists a pivot $x\in B$ with
$d(s,x,e)\leqslant\varepsilon\operatorname{diam}(G)$.

######  Proof 3.4.

If $d(s,r)\leqslant\varepsilon\operatorname{diam}(G)$, we are done. Otherwise,
let $P$ be the prefix of length $\ell$ of the path from $s$ to $r$ in the tree
$T_{\text{in}}(r)$, whence $P\in\mathcal{P}$. If $P$ does not contain the edge
$e$, it also exists in $G\,{-}\,e$ and the corresponding pivot $x\in B\cap
V(P)$ satisfies
$d(s,x,e)=d(s,x)\leqslant\ell\leqslant\varepsilon\operatorname{diam}(G)$. If
$P$ contains $e$, then let instead $P^{\prime}\in\mathcal{P}_{e}$ be the
length-$\ell$ prefix of the path from $s$ to $r$ in $T_{\text{in},e}(r)$.
Again, $x\in B\cap V(P^{\prime})$ implies
$d(s,x,e)\leqslant\varepsilon\operatorname{diam}(G)$.

###  3.3 Space Lower Bounds

Finally, we prove Theorem 1.1 thus showing that the space requirement of the
FDOs in Theorems 1.2 and 1.3 is near-optimal provided that the stretch is
$\sigma=\sigma(m,n)<3/2$, that is, $\varepsilon<1/2$. This even holds for the
simpler task of computing the diameter in undirected graphs. For better
exposition, we first show that any diameter oracle with such a stretch
requires $\Omega(n^{2})$ space on at least one $n$-vertex graph, which is,
however, only tight for dense graphs. We then sparsify the construction to for
an $\Omega(m)$ bound for graphs with $m$ edges. Any $\sigma$-approximate FDO
solves the promise problem of distinguishing, for each edge $e$, whether
$G\,{-}\,e$ has diameter $2$ or $3$.

######  Lemma 3.5.

There is a graph $G$ on $n$ vertices such that $G\,{-}\,e$ has diameter $2$ or
$3$ for any $e\in E$. Any data structure that decides which one is the case
must take $\Omega(n^{2})$ bits of space.

######  Proof 3.6.

We give an incompressibility argument by encoding any binary $(n/4)\hskip
1.00006pt{\times}\hskip 1.00006pt(n/4)$ matrix $X$ in the fault-tolerant
diameters of $G$. No data structure can store this in $o(n^{2})$ bits. The
construction is illustrated in 1(a).

Without loosing generality, $n$ is divisible by $4$, we can add up to three
dummy vertices if needed. Split the vertex set equally into four groups $A$,
$B$, $C$, $D$ and let $a_{1},\dots,a_{n/4}$ be an arbitrary numbering of the
elements of $A$, same with the other groups. All groups are made into cliques
and, for all $i\in[n/4]$, we make $a_{i}$, $b_{i}$, and $c_{i}$ into a
triangle. This results in matchings for the pairs $(A,B)$, $(B,C)$, and
$(A,C)$, respectively. We further add edges so as to make $(B,D)$ into a
biclique. To encode the matrix $X$, we introduce the edge $\\{c_{i},d_{j}\\}$
if and only if $X_{i,j}=1$.

The graph $G$ indeed has diameter $2$ (even if $X$ is the all-zeros matrix).
Vertices $a_{i}$ and $b_{j}$ are joined by the path $(a_{i},a_{j},b_{j})$ –
which by symmetry also holds for the other pairs of groups among $A$, $B$, or
$C$ – and and the vertices $a_{i}$ or $c_{i}$ are connected to $d_{j}$ via the
paths $(a_{i},b_{i},d_{j})$ or $(c_{i},b_{i},d_{j})$, respectively. Removing
any edge increases the diameter by at most $1$ since for any $e=\\{u,v\\}$
there exists a common neighbor in $w\in N[u]\cap N[v]$. This is clear inside
the (bi-)cliques. For the matching edges, say $e=\\{a_{i},b_{i}\\}$, we have
$w=a_{j}$, $j\neq i$. Finally, for $e=\\{c_{i},d_{j}\\}$ (if it exists), we
have $w=b_{i}$.

We now prove that the graph $G-\\{b_{i},d_{j}\\}$ has diameter $3$ if and only
if the edge $\\{c_{i},d_{j}\\}$ is _not_ present in $G$, that is, iff
$X_{i,j}=0$. When arguing the diameter above, edge $\\{b_{i},d_{j}\\}$ was
only needed for the paths $(a_{i},b_{i},d_{j})$ and $(c_{i},b_{i},d_{j})$.
Consider the neighborhoods of the three vertices in $G-\\{b_{i},d_{j}\\}$,
$N[a_{i}]=A\cup\\{c_{i},d_{i}\\}$,
$N[c_{i}]=C\cup\\{a_{i},b_{i}\\}\cup\\{d_{k}\mid X_{i,k}=1\\}$, and
$N[d_{j}]=D\cup(B{\setminus}\\{b_{i}\\})\cup\\{c_{k}\mid X_{k,j}=1\\}$. If
$X_{i,j}=1$, then the neighborhoods intersect, namely in $c_{i}$, keeping the
diameter at $2$. If, however, $X_{i,j}=0$, then $N[a_{i}]\cap
N[d_{j}]=\emptyset$ and the diameter increases to $3$.

(a)

(b)

Figure 1: Illustration of 3.5 (1(a)) and of 3.7 (1(b)). The full ellipses $A$,
$B$, $C$, $D$ are cliques on the respective number of vertices, the dashed
ellipse $R$ is an independent set. The three parallel lines stand for
matchings, the two crossed lines for a biclique. Edges encoding the binary
matrix $X$ run between $C$ and $D$. Every vertex $r\in R$ is connected to
$a_{1}\in A$, $b_{1}\in B$, and $c_{1}\in C$.

We now refine the result to give a better bound for sparse graphs. Note that a
logarithmic gap remains between 3.7 and Theorem 1.2 since we lower bound the
space at $\Omega(m)$ bits while the FDO takes this many words.

######  Lemma 3.7.

There is a graph $G$ with $m$ edges such that $G\,{-}\,e$ has diameter $2$ or
$3$ for any edge $e\in E$. A data structure that decides which one is the case
must take $\Omega(m)$ bits of space.

######  Proof 3.8.

The main weakness of the construction in 3.5 is that it requires
$\Omega(n^{2})$ edges inside the cliques. As it turns out, this is not
necessary and we can sparsify the graph $G$ as long as we keep its diameter at
$2$. 1(b) shows the idea of the sparsification.

Let $m^{\prime}$ be a parameter to be fixed later. We now store a binary
$\mathchoice{{\hbox{$\displaystyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\textstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\scriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=4.125pt,depth=-3.30002pt}}}{{\hbox{$\scriptscriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=3.26389pt,depth=-2.61113pt}}}\times\mathchoice{{\hbox{$\displaystyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\textstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\scriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=4.125pt,depth=-3.30002pt}}}{{\hbox{$\scriptscriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule height=3.26389pt,depth=-2.61113pt}}}$ matrix $X$. Split the
vertices into five groups, where $A$, $B$, $C$, $D$ each contain
$\textstyle\sqrt{m^{\prime}\,}$ vertices and $R$ the remaining
$n-4\mathchoice{{\hbox{$\displaystyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\textstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\scriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=4.125pt,depth=-3.30002pt}}}{{\hbox{$\scriptscriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule height=3.26389pt,depth=-2.61113pt}}}$. The edges among
vertices in $A$ through $D$ are the same as in 3.5. Each vertex in $R$ has
degree $3$ and is connected to $a_{1}$, $b_{1}$, and $c_{1}$. The graph $G$
has $4\binom{\mathchoice{{\hbox{$\displaystyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\textstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\scriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=4.125pt,depth=-3.30002pt}}}{{\hbox{$\scriptscriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=3.26389pt,depth=-2.61113pt}}}}{2}+3\mathchoice{{\hbox{$\displaystyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\textstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\scriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=4.125pt,depth=-3.30002pt}}}{{\hbox{$\scriptscriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=3.26389pt,depth=-2.61113pt}}}+m^{\prime}+|\\{(i,j)\mid
X_{i,j}=1\\}|+3(n-4\mathchoice{{\hbox{$\displaystyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\textstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=5.8611pt,depth=-4.6889pt}}}{{\hbox{$\scriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule
height=4.125pt,depth=-3.30002pt}}}{{\hbox{$\scriptscriptstyle\sqrt{m^{\prime}\,}$}\lower
0.4pt\hbox{\vrule height=3.26389pt,depth=-2.61113pt}}})=O(m^{\prime})$ edges.
We fix the parameter $m^{\prime}$ such that the total number of edges is $m$.
If needed, we introduce additional edges among vertices in $R$ without
affecting the result.

Note that the eccentricity of any vertex in $r\in R$ is $2$ (even if $R$ is
not an independent set). Vertex $a_{i}$ is reached via the path
$(r,a_{1},a_{i})$, similar for the vertices in $B$ and $C$, the ones in $D$
are reached via $b_{1}$. Moreover, for any edge involving $r$, say
$\\{r,a_{1}\\}$, we have $b_{1}\in N[r]\cap N[a_{1}]$. Therefore, the proof
that $G$ has diameter $2$, $G-e$ has diameter $2$ or $3$, and
$G-\\{b_{i},d_{j}\\}$ has diameter $3$ iff $X_{i,j}=0$ is almost exactly as in
3.5. The sole difference is the case in which the edge $\\{b_{1},d_{j}\\}$
fails since this may also increase the eccentricity of $r$. This is settled by
observing that the neighborhood $N[r]=\\{r,a_{1},b_{1},c_{1}\\}$ in
$G-\\{b_{1},d_{j}\\}$ intersects $N[d_{j}]$ iff $X_{1,j}=1$. To accommodate
all possible matrices $X$, we require $\Omega(m^{\prime})=\Omega(m)$ bits.

The same construction shows that for edge-weighted graphs there is no
$(2{-}\varepsilon)$-approximate FDO, for any $\varepsilon=\varepsilon(m)>0$,
with space $o(m)$. In more detail, we choose an $\varepsilon^{\prime}>0$ small
enough so that $\varepsilon^{\prime}<2\varepsilon/(1-\varepsilon)$ and give
weight $\varepsilon^{\prime}$ to all matching edges as well as the edges
incident to vertices in $R$, all other edges are weighted $2$. One can verify
that $\operatorname{diam}(G)=2+\varepsilon^{\prime}$ and the fault-tolerant
diameter $\operatorname{diam}(G-\\{b_{i},d_{j}\\})$ remains at that value iff
$\\{c_{i},d_{j}\\}$ is present, it raises to $4+\varepsilon^{\prime}$
otherwise. The bound on the stretch cannot be improved as shown by the trivial
FDO discussed in the introduction, which gives a $2$-approximation in $O(n)$
space.

##  4 Multiple Edge Failures

We now turn to multiple edge failures. Recall that in the fault-tolerant
setting the maximum number $f$ of failures is known in advance, and stretch,
space, preprocessing, and query time usually depend on $f$. In this section,
we first prove the following lemma. Let $\alpha=\alpha(m,n)$ denote the
inverse Ackermann function.

######  Lemma 4.1 (Theorem 1.5 with explicit logarithmic factors).

For every undirected graph with non-negative edge weights, there exists a
deterministic combinatorial $(f\,{+}\,2)$-approximate $f$-FDO that takes
$O(fn\log^{2}\\!n)$ space and has $O(fm\hskip 1.00006pt\alpha+fn\log^{3}\\!n)$
preprocessing time and $O(f^{2}\log^{2}\\!n)$ query time. For $f=1$, the size
of the oracle is $O(n)$, the preprocessing time $O(m\hskip
1.00006pt\alpha+n\log n)$, and the query time is constant.

Bilò et al. [9] designed an $(2f{+}1)$-approximate single-source $f$-DSO. That
means, the oracle processes an undirected graph $G$ with non-negative edge
weights and a distinguished source $s$, and, upon query $(t,F)$ with
$|F|\leqslant f$, it returns $d(s,t,F)$. The oracle can be built in
$O\big{(}fm\alpha+fn\log^{3}n\big{)}$ time, has size $O(fn\log^{2}n)$, and
answers queries in $O(f^{2}\log^{2}n)$ time. In principle we can modify the
oracle so as, when queried with the set $F$, it returns twice the eccentricity
of $s$ in the graph $G\,{-}\,F$. This would clearly allow us to construct an
$f$-FDO of stretch $2{\cdot}(2f{+}1)$. We show that the same oracle
construction, but with a better query algorithm, allows us to develop an
$f$-FDO of stretch $f+2$.

We let $w(e)$ denote the weight of the edge $e\in E$. The length of a path is
now defined as the sum of its edge weights; the definitions of distance and
diameter are adjusted accordingly. The oracle in [9] first computes a shortest
path tree $T$ of $G$ rooted at the source $s$ and uses it to re-weight all the
edges of $G$. The new weight function $w^{\prime}$ assigns weight of $0$ to
each edge of $T$ and weight $w^{\prime}(e)=d(s,x)+w(e)+d(y,s)$ to any other
edge $e=\\{x,y\\}$. When queried with $(t,F)$, the oracle computes a spanning
forest $T_{F}$ of $G\,{-}\,F$ w.r.t. the new weight function $w^{\prime}$ in
$O(f^{2}\log^{2}n)$ time. Let $k=|F\cap E(T)|$. The oracle replaces the $k$
failing edges in $F\cap E(T)$ with a minimum-weight set of edges in
$G\,{-}\,F$ w.r.t. to $w^{\prime}$, say $E_{F}$, whose addition to $T\,{-}\,F$
forms a spanning forest of $G\,{-}\,F$.777This is done by computing, for each
unordered pair $\phi=(T^{\prime},T^{\prime\prime})$ of connected components of
$T-F$, the minimum-weight edge w.r.t. $w^{\prime}$, say $e_{\phi}$, that has
one endpoint in $T^{\prime}$ and the other endpoint in $T^{\prime\prime}$.
Then, the set $E_{F}$ is computed in $O(f^{2})$ time using any time-efficient
algorithm for computing a minimum spanning tree of an auxiliary graph in which
each of the connected components of $T-F$ is modelled by a vertex and the edge
between the unordered pair $\phi=(T^{\prime},T^{\prime\prime})$ of $T-F$ has a
weight equal to $w^{\prime}(e_{\phi})$. The authors of [9] design a data
structure that is able to retrieve, for each pair
$\phi=(T^{\prime},T^{\prime\prime})$ of connected components of $T-F$, the
edge $e_{\phi}$ in $O(\log^{2}n)$ time.  The obtained forest $T_{F}$ is then
used to estimate the distance from $s$ to $t$ in $G\,{-}\,F$. We reuse a nice
property proven in [9].

######  Lemma 4.2 (Bilò et al. [9]).

$T_{F}$ is a minimum spanning forest of $G\,{-}\,F$ w.r.t. $w^{\prime}$.

Our query algorithm works as follows. Let tree $T$ be rooted at $s$ and $F\cap
E(T)=\\{f_{1},\dots,f_{k}\\}$ with $k\leqslant f$ the edges in $T$ that are
also in $F$. Let $T_{0},\dots,T_{k}$ denote the $k+1$ subtrees of $T\,{-}\,F$,
and $r_{i}$ the root of the subtree $T_{i}$. W.l.o.g., we assume $r_{0}=s$. We
use $f_{1},\dots,f_{k}$ to compute the roots $r_{1},\dots,r_{k}$ in $O(k)$
time. We then build a forest $T^{\prime}$ on $k+1$ new vertices
$v_{0},\dots,v_{k}$, where $v_{i}$ represents $T_{i}$. The forest $T^{\prime}$
contains an edge $\\{v_{i},v_{j}\\}$ iff $E_{F}$ contains an edge $e$ with one
end point in $V(T_{i})$ and the other in $V(T_{j})$. Obviously, if
$T^{\prime}$ is not connected, then we can simply certify that
$\operatorname{diam}(G\,{-}\,F)=\infty$. So, we assume that $T^{\prime}$ is a
tree. We root $T^{\prime}$ at $v_{0}$ and denote by $e_{i}$ the edge that
joins $v_{i}$ with its parent $p(v_{i})$. We compute the value
$\Delta=\max_{1\leqslant i\leqslant k}w^{\prime}(e_{i})-d(s,r_{i})$ and output
$\widehat{D}=f\Delta+2\cdot\max_{t\in V}d(s,t)$. The time needed for the query
algorithm is dominated by the computation of $T$ in time $O(f^{2}\log^{2}n)$
as all the new operations can be performed in $O(f^{2})$ time. Observe that
$\max_{t\in V}d(s,t)$ is independent of $F$ and can be precomputed in time
$O(n)$.

For a single failure, $f=1$, the query time can be reduced to $O(1)$. In fact,
for each edge $e$ of $T$, it is enough to precompute the minimum weight edge
of $E(G){\setminus}E(T)$, w.r.t. weight function $w^{\prime}$, that crosses
the cut induced by $T-e$. This, a.k.a. the sensitivity analysis problem of a
minimum spanning tree, can be solved in $O(m\log\alpha)$ time on a graph with
$m$ edges [38]. We show in the remainder that $\widehat{D}$ is an
$(f+2)$-approximation of $\operatorname{diam}(G-F)$. The proof of the
following lemma can be found in Appendix B.

######  Lemma 4.3.

We have that $\operatorname{diam}(G-F)\geqslant\Delta$.

We now prove the approximation with the help of 4.3.

######  Lemma 4.4.

The value $\widehat{D}$ satisfies
$\operatorname{diam}(G-F)\leqslant\widehat{D}\leqslant(f+2)\operatorname{diam}(G-F)$.

######  Proof 4.5.

Again, we only need to prove anything if $T^{\prime}$ is connected, which
implies that $T_{F}$ is connected. By 4.3, we have that
$\operatorname{diam}(G\,{-}\,F)\geqslant\Delta$. Moreover,
$\operatorname{diam}(G\,{-}\,F)\geqslant\operatorname{diam}(G)\geqslant\max_{t\in
V}d(s,t)$. The value $\widehat{D}$ returned by the query algorithm satisfies
$\widehat{D}\leqslant f\Delta+2\max_{t\in
V}d(s,t)\leqslant(f\,{+}\,2)\operatorname{diam}(G-F)$. It remains to show that
$\widehat{D}\geqslant\operatorname{diam}(G\,{-}\,F)$. We prove the latter by
verifying that, for any two vertices $x$ and $y$, $\widehat{D}\geqslant
d(x,y,F)$ holds.

Let $r_{x}$ and $r_{y}$ be the roots of the subtrees of $T\,{-}\,F$ that
contain $x$ and $y$, respectively. It is possible that $r_{x}=r_{y}$. Let
$r_{p(i)}$ denote the root of the tree of $T\,{-}\,F$ that corresponds to the
parent vertex $p(v_{i})$ in $T^{\prime}$. Consider the subgraph of $T_{F}$
consisting of the edges of the paths in $T_{F}$ between the following pairs of
vertices: (a) $r_{p(i)}$ and $r_{i}$ for every $i$, (b) $x$ and $r_{x}$, (c)
$y$ and $r_{y}$. The subgraph contains a path from $x$ to $y$ since $T_{F}$ is
connected. Therefore, the replacement distance $d(x,y,F)$ is upper bounded by
the total weight of the subgraph. The path in $T_{F}$ between $r_{x}$ and $x$
has length at most $\max_{t\in V}d(s,t)$ as $r_{x}$ is an ancestor of $x$ in
the shortest path tree $T$ rooted at $s$; same for $r_{y}$ and $y$. Finally,
for any $i>0$, let $e_{i}=\\{x_{i},y_{i}\\}$ be the edge in $E_{F}$ that
caused the addition of the edge $(v_{i},p(v_{i}))$ in $T^{\prime}$. W.l.o.g.,
we assume that $x_{i}$ (resp., $y_{i}$) is a vertex of the tree of $T\,{-}\,F$
represented by $v_{i}$ (resp., $p(v_{i})$) in $T^{\prime}$. The path from
$r_{i}$ to $r_{p(i)}$ in $G-F$ has length at most
$d(r_{i},x_{i})+w(e_{i})+d(y_{i},r_{p(i)})\leqslant
d(r_{i},x_{i})+w(e_{i})+d(y_{i},s)+d(s,r_{i})-d(s,r_{i})=w^{\prime}(e_{i})-d(s,r_{i})\leqslant\Delta$.
Therefore, $d(x,y,F)\leqslant k\Delta+2\max_{t\in V}d(s,t)\leqslant
f\Delta+2\max_{t\in V}d(s,t)=\widehat{D}$.

###  4.1 Exact $f$-FDO for Low Diameter

We show that one can swap approximation for query time in low-diameter graphs,
namely, with diameter at most $n^{\delta/f}/(f{+}1)$ for arbitrary
$\delta=\delta(m,n)>0$. This is summarized in Theorem 1.6. The case
$f\,{=}\,1$ is solved like in Section 3.1 only that there is no need for
approximation here as the diameter is small enough to process all pairs of
vertices in time $O(n^{2+\delta})$. We thus assume $f\geqslant 2$. We adapt a
space-saving technique introduced by Chechik et al. [13]. In a bird’s-eye
view, we construct a recursion tree $T(s,t)$ of size $O(n^{\delta})$ for each
pair of vertices $s$ and $t$. It contains all _relevant_ replacement distances
$d(s,t,F)$ for sets $F$ with up to $f$ failures. We then show how we can
simulate the search for $\operatorname{diam}(G\,{-}\,F)$ in the $O(n^{2})$
trees in total time $O(2^{f})$.

Afek et al. [1, Theorem 1] showed that if $G$ is undirected, then any shortest
path in $G\,{-}\,F$, with $|F|$, is a concatenation of at most $|F|+1$
shortest paths in $G$. The condition on the diameter and $|F|\leqslant f$
ensure that every path below has length at most
$(f{+}1)\cdot\operatorname{diam}(G)\leqslant n^{\delta/f}$.

Assume we have access to a path-reporting $f$-DSO. That means, upon query
$(s,t,F)$, the oracle either certifies that $d(s,t,F)=\infty$, i.e., $s$ and
$t$ are disconnected in $G\,{-}F$, or reports the replacement distance and a
shortest $s$-$t$-path in $G\,{-}F$. The preprocessing time of the
combinatorial version is assumed to be $\widetilde{O}(fmn^{1+\delta})$ with a
$\widetilde{O}(fn^{(1-1/f)\delta}+|P|\hskip
1.00006pt)=\widetilde{O}(fn^{(1-1/f)\delta})$ query time w.h.p. reporting path
$P$. Here, we used the assumption $f\geqslant 2$, whence $|P|\leqslant
n^{\delta/f}=\widetilde{O}(fn^{(1-1/f)\delta})$. Alternatively, we have
algebraic preprocessing in time $\widetilde{O}(fn^{\omega+\delta})$. We show
how to obtain the oracle in Appendix C, using an idea of Weimann and Yuster
[44] with a more refined analysis of the query time.

Fix two vertices $s$ and $t$. We construct the tree $T(s,t)$ recursively. Each
node in the tree is associated with a set $F\subseteq\binom{V}{2}$ containing
$f^{\prime}=|F^{\prime}|\leqslant f$ possible failures. We have
$F^{\prime}=\emptyset$ in the root. Upon creation, the node queries the
assumed oracle with $(s,t,F^{\prime})$ and holds the returned path
$P(s,t,F^{\prime})$, if any. If $f^{\prime}=f$ or $s$ and $t$ are disconnected
in $G\,{-}\,F^{\prime}$, the node is a leaf. Otherwise, it has
$d(s,t,F^{\prime})$ many children, one for each edge of $e\in
E(P(s,t,F^{\prime}))$ of the path. The respective child is associated with the
set $F^{\prime}\cup\\{e\\}$.

The tree indeed has at least one node for every distinct replacement distance
$d(s,t,F)$ with $|F|\leqslant f$. To see this, let $F^{\prime},F$ be two sets
with $F^{\prime}\subseteq F\subseteq\binom{V}{2}$. Clearly, we have
$d(s,t,F^{\prime})\leqslant d(s,t,F)$, but $d(s,t,F^{\prime})<d(s,t,F)$ can
only hold if $F{\setminus}F^{\prime}$ contains an edge of the path
$P(s,t,F^{\prime})$ in the node associated with $F^{\prime}$. The fan-out of
each node is at most $n^{\delta/f}$, the height of the tree is $f$. For all
$s,t\in V$, the trees thus have $O(n^{2+\delta})$ nodes in total and can be
constructed with that many queries to the $f$-DSO in time
$\widetilde{O}(fn^{2+(2-1/f)\delta})$.

Consider the following naive algorithm to handle a query to the $f$-FDO for
the fault-tolerant diameter $\operatorname{diam}(G\,{-}\,F)$. Each tree
$T(s,t)$ is searched individually starting in the root. The processing of a
node depends on the associated set $F^{\prime}$. If it is a leaf or the set
$F{\setminus}F^{\prime}$ is disjoint from the replacement path
$P(s,t,F^{\prime})$, then we return the length $d(s,t,F^{\prime})$ of the
path; otherwise, we recurse on all children associated with
$F^{\prime}\cup\\{e\\}$ for all edges $e\in(F{\setminus}F^{\prime})\cap
E(P(s,t,F^{\prime}))$. By the argument as above, the maximum over all reported
distances is indeed $\max_{s,t\in V;F^{\prime}\subseteq
F}d(s,t,F^{\prime})=\operatorname{diam}(G\,{-}\,F)$. This approach can be
improved significantly by aggregating the values
$\\{d(s,t,F^{\prime})\\}_{s,t\in V}$ already at construction.

Observe that we never query the underlying $f$-DSO with a set $F^{\prime}$
that contains non-edges. We prepare a hash table $H$ whose entries are indexed
by subsets of $E$ of size at most $f$. For every query $(s,t,F^{\prime})$ we
compare the returned replacement distance with the value $H[F^{\prime}]$. If
no such entry exists, we initialize it with $d(s,t,F^{\prime})$; else, we
update it to $\max\\{H[F^{\prime}],d(s,t,F^{\prime})\\}$. The final table has
size $O(n^{2+\delta})$ and we discard the trees. The table $H$ is
constructible w.h.p. in time $O(n^{2+\delta})$, guaranteeing constant query
time [20, 37]. However, to simulate the naive algorithm for the query $F$ to
the $f$-FDO, we have to check $H[F^{\prime}]$ for all $O(2^{f})$ subsets
$F^{\prime}\subseteq F$ as we do not know which ones were used during
construction.

###  4.2 Space Lower Bound

We conclude with the space lower bound of Theorem 1.4. It rules out any finite
stretch in $o(fn)$ space for an arbitrary number $f$ of failures. We use the
fact that an $f$-FDO with finite stretch is able to decide whether the edges
in $F$ are a cut-set of the graph.

Assume for now that $f$ is even. Let $k$ be the largest integer such that
$fk+1\leqslant n$. We construct a graph $G$ as follows. It has vertices
$c,v_{1},\dots,v_{fk}$ as well as $n\,{-}\,fk\,{-}\,1$ auxiliary vertices.
Define $E_{i}=\\{\\{v_{i},v_{j}\\}\mid 1\leqslant|i-j|\leqslant f/2\\}$. The
edge set of $G$ is $\bigcup_{i=1}^{fk}E_{i}$ together with all possible edges
$\\{c,u\\}$, including to the auxiliaries. In other words, $G$ consists of a
star centered at $c$ with $n-1$ leaves, and leaves $v_{i},v_{j}$ are joined by
an edge iff their indices have difference at most $f/2$. Let set $\mathcal{G}$
contain all spanning subgraphs of $G$ that retain at least all star edges
incident to $c$. Since $|E_{i}|=f$, there are
$|\mathcal{G}|=2^{(f{-}1)fk/2}=2^{\Omega(fn)}$ such subgraphs.

Let $H$ be any subgraph in $\mathcal{G}$. For $i\neq j$ with $|i-j|\leqslant
f/2$, define the set
$F_{i,j}=(E_{i}{\setminus}\\{\\{v_{i},v_{j}\\}\\})\cup\\{\\{c,v_{i}\\}\\}$.
Note that $F_{i,j}$ may contain non-edges. We have $|F_{i,j}|=f$ and evidently
$\\{v_{i},v_{j}\\}$ is present in $H$ iff $H-F_{i,j}$ is connected. Any two
$f$-FDOs for graphs in $\mathcal{G}$ thus differ in at least one bit. For odd
values $f\geqslant 3$, we emulate this using $f-1$ failures.

For the remaining case $f=1$, we use a different construction. W.l.o.g., $n$
is even, connecting a single excess vertex to some other vertex in the graph
is immaterial. The graph $G$ contains two parallel paths $P_{1}$ and $P_{2}$,
each on $n/2$ vertices, respectively numbered from $1$ to $n/2$. The graph
also contains a matching $M$ in which the $i$-th vertex of $P_{1}$ is matched
with the $i$-th vertex of $P_{2}$. Let $\mathcal{G}$ be the set of all
spanning subgraphs that have at least all the edges of $P_{1}$ and $M$. We
have $|\mathcal{G}|=2^{(n/2)-1}=2^{\Omega(n)}$. Let $H\in\mathcal{G}$ and
define $e_{i}$, with $i<n/2$, be the edge of $P_{1}$ between the $i$-th and
$(i{+}1)$-th vertices. The corresponding edge of $P_{2}$ is present in $H$ if
and only $H-e_{i}$ is connected.

## References

  * [1] Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, and Michael Merritt.  Restoration by Path Concatenation: Fast Recovery of MPLS Paths.  Distributed Computing, 15:273–283, 2002.  doi:10.1007/s00446-002-0080-6.
  * [2] Josh Alman and Virginia Vassilevska Williams.  A Refined Laser Method and Faster Matrix Multiplication.  In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA), pages 522–539, 2021.  doi:10.1137/1.9781611976465.32.
  * [3] Noga Alon, Shiri Chechik, and Sarel Cohen.  Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 12:1–12:14, 2019.  doi:10.4230/LIPIcs.ICALP.2019.12.
  * [4] Noga Alon and Moni Naor.  Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.  Algorithmica, 16:434–449, 1996.  doi:10.1007/BF01940874.
  * [5] Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares.  On Sparse Spanners of Weighted Graphs.  Discrete and Computational Geometry, 9:81–100, 1993.  doi:10.1007/BF02189308.
  * [6] Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein.  Algorithms and Hardness for Diameter in Dynamic Graphs.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 13:1–13:14, 2019.  doi:10.4230/LIPIcs.ICALP.2019.13.
  * [7] Surender Baswana and Telikepalli Kavitha.  Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs.  SIAM Journal on Computing, 39:2865–2896, 2010.  doi:10.1137/080737174.
  * [8] Aaron Bernstein and David R. Karger.  A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges.  In Proceedings of the 41st Symposium on Theory of Computing (STOC), pages 101–110, 2009.  doi:10.1145/1536414.1536431.
  * [9] Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti.  Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees.  In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 18:1–18:14, 2016.  doi:10.4230/LIPIcs.STACS.2016.18.
  * [10] Édouard Bonnet.  4 vs 7 Sparse Undirected Unweighted Diameter is SETH-hard at Time $n^{4/3}$.  In Proceedings of 48th International Colloquium on Automata, Languages, and Programming, (ICALP), 2021.  To appear.
  * [11] Shiri Chechik and Sarel Cohen.  Near Optimal Algorithms for the Single Source Replacement Paths Problem.  In Proceedings of the 30th Symposium on Discrete Algorithms (SODA), pages 2090–2109, 2019.  doi:10.1137/1.9781611975482.126.
  * [12] Shiri Chechik and Sarel Cohen.  Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time.  In Proccedings of the 52nd Symposium on Theory of Computing (STOC), pages 1375–1388, 2020.  doi:10.1145/3357713.3384253.
  * [13] Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan.  (1 + $\epsilon$)-Approximate $f$-Sensitive Distance Oracles.  In Proceedings of the 28th Symposium on Discrete Algorithms (SODA), pages 1479–1496, 2017.  doi:10.1137/1.9781611974782.96.
  * [14] Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert E. Tarjan, and Virginia Vassilevska Williams.  Better Approximation Algorithms for the Graph Diameter.  In Proceedings of the 25th Symposium on Discrete Algorithms (SODA), pages 1041–1052, 2014.  doi:10.1137/1.9781611973402.78.
  * [15] Shiri Chechik and Ofer Magen.  Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem.  In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 81:1–81:17, 2020.  doi:10.4230/LIPIcs.ICALP.2020.81.
  * [16] Keerti Choudhary and Omer Gold.  Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms.  In Proceedings of the 31st Symposium on Discrete Algorithms (SODA), pages 495–514, 2020.  doi:10.1137/1.9781611975994.30.
  * [17] Fan Chung and Linyuan Lu.  The Average Distances in Random Graphs with Given Expected Degrees.  Proceedings of the National Academy of Sciences, 99:15879–15882, 2002.  doi:10.1073/pnas.252631999.
  * [18] Edith Cohen and Uri Zwick.  All-Pairs Small-Stretch Paths.  Journal of Algorithms, 38:335–353, 2001.  doi:10.1006/jagm.2000.1117.
  * [19] Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran.  Oracles for Distances Avoiding a Failed Node or Link.  SIAM Journal on Computing, 37:1299–1318, 2008.  doi:10.1137/S0097539705429847.
  * [20] Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert E. Tarjan.  Dynamic Perfect Hashing: Upper and Lower Bounds.  SIAM Journal on Computing, 23:738–761, 1994.  doi:10.1137/S0097539791194094.
  * [21] Ran Duan, Yong Gu, and Hanlin Ren.  Approximate Distance Oracles Subject to Multiple Vertex Failures.  In PProceedings of the 32nd Symposium on Discrete Algorithms (SODA), pages 2497–2516, 2021.  doi:10.1137/1.9781611976465.148.
  * [22] Ran Duan and Seth Pettie.  Dual-Failure Distance and Connectivity Oracles.  In Proceedings of the 20th Symposium on Discrete Algorithms (SODA), pages 506–515, 2009.  URL: https://dl.acm.org/citation.cfm?id=1496770.1496826.
  * [23] Ran Duan and Tianyi Zhang.  Improved Distance Sensitivity Oracles via Tree Partitioning.  In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS), pages 349–360, 2017.  doi:10.1007/978-3-319-62127-2_30.
  * [24] Tobias Friedrich and Anton Krohmer.  On the Diameter of Hyperbolic Random Graphs.  SIAM Journal on Discrete Mathematics, 32:1314–1334, 2018.
  * [25] Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann.  Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic _Õ_(_n_ ${}^{\mbox{5/3}}$) Time.  In Proceedings of the 29th Symposium on Discrete Algorithms (SODA), pages 495–514, 2018.  doi:10.1137/1.9781611975031.33.
  * [26] Fabrizio Grandoni and Virginia Vassilevska Williams.  Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths.  In Proceedings of the 53rd Symposium on Foundations of Computer Science (FOCS), pages 748–757, 2012.  doi:10.1109/FOCS.2012.17.
  * [27] Fabrizio Grandoni and Virginia Vassilevska Williams.  Faster Replacement Paths and Distance Sensitivity Oracles.  ACM Transaction on Algorithms, 16:15:1–15:25, 2020.  doi:10.1145/3365835.
  * [28] Yong Gu and Hanlin Ren.  Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time.  In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021.  To appear.
  * [29] Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh.  Deterministic Dictionaries.  Journal of Algorithms, 41:69–85, 2001.  doi:10.1006/jagm.2001.1171.
  * [30] Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams.  Conditional Hardness for Sensitivity Problems.  In Proceedings of the 8th Conference on Innovations in Theoretical Computer Science (ITCS), pages 26:1–26:31, 2017.  doi:10.4230/LIPIcs.ITCS.2017.26.
  * [31] Remco van der Hofstad.  Random Graphs and Complex Networks, volume 1 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, UK, 2016.  doi:10.1017/9781316779422.
  * [32] Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni.  Finding Strong Bridges and Strong Articulation Points in Linear Time.  Theoretical Computer Science, 447:74–84, 2012.  doi:10.1016/j.tcs.2011.11.011.
  * [33] Telikepalli Kavitha.  Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs.  Algorithmica, 63:224–245, 2012.  doi:10.1007/s00453-011-9529-y.
  * [34] Valerie King.  Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs.  In Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS), pages 81–91, 1999.  doi:10.1109/SFFCS.1999.814580.
  * [35] Jon M. Kleinberg.  Navigation in a Small World.  Nature, 406:845–845, 2000.  doi:10.1038/35022643.
  * [36] Michael Mitzenmacher and Eli Upfal.  Probability and Computing.  Cambridge University Press, New York, NY, USA, 2nd edition, 2017.
  * [37] Rasmus Pagh and Flemming Friche Rodler.  Cuckoo Hashing.  Journal of Algorithms, 51:122–144, 2004.  doi:10.1016/j.jalgor.2003.12.002.
  * [38] Seth Pettie.  Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time.  Journal of Graph Algorithms and Applications, 19:375–391, 2015\.  doi:10.7155/jgaa.00365.
  * [39] Hanlin Ren.  Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.  In Proceedings of the 28th European Symposium on Algorithms (ESA), pages 79:1–79:13, 2020.  doi:10.4230/LIPIcs.ESA.2020.79.
  * [40] Hanlin Ren.  Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.  CoRR, abs/2007.11495, 2020.  ArXiv preprint. Full version of [39].  arXiv:2007.11495.
  * [41] Liam Roditty.  Approximating the Diameter.  In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 116–117. Springer, New York City, NY, USA, 2016.  doi:10.1007/978-1-4939-2864-4_566.
  * [42] Liam Roditty and Uri Zwick.  Replacement Paths and $k$ Simple Shortest Paths in Unweighted Directed Graphs.  ACM Transaction on Algorithms, 8:33:1–33:11, 2012.  doi:10.1145/2344422.2344423.
  * [43] Mikkel Thorup and Uri Zwick.  Approximate Distance Oracles.  In Proceedings on 33rd Symposium on Theory of Computing (STOC), pages 183–192, 2001.  doi:10.1145/380752.380798.
  * [44] Oren Weimann and Raphael Yuster.  Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication.  ACM Transactions on Algorithms, 9:14:1–14:13, 2013.  doi:10.1145/2438645.2438646.
  * [45] Uri Zwick.  All Pairs Shortest Paths Using Bridging Sets and Rectangular Matrix Multiplication.  Journal of the ACM, 49:289–317, 2002.  doi:10.1145/567112.567114.

##  Appendix A Proofs Omitted in section 2

See 2.1

######  Proof A.1.

The bounds on the query time and the size are by construction. We prove the
upper bound on the stretch. For every edge $e\in E(H)$ the oracle reports the
exact value $\operatorname{diam}(G-e)$. Therefore, we only need to bound the
approximation guarantee when the failing edge $e\not\in E(H)$. Let $e=(u,v)$.
We have that $d(u,v,e)\leqslant 2k-1$. As a consequence, any path of length
$\ell$ that uses edge $e$ in $G$ has a length that is at most $\ell+2(k-1)$ in
$G-e$ as we can bypass the edge $e$ by the path between $u$ and $v$ in $G-e$
of length at most $2k-1$. Therefore,
$\operatorname{diam}(G-e)\leqslant\operatorname{diam}(G)+2(k-1)$. This implies
that the value $\widehat{D}=\operatorname{diam}(G)+2(k-1)$ returned by the
query oracle satisfies
$\operatorname{diam}(G-e)\leqslant\widehat{D}\leqslant\operatorname{diam}(G)+2(k-1)$.
Therefore, using the fact that
$\operatorname{diam}(G-e)\geqslant\operatorname{diam}(G)$, the stretch of the
oracle is $1+2(k-1)/\operatorname{diam}(G)$.

##  Appendix B Proofs Omitted in section 4

See 4.3

######  Proof B.1.

If $\operatorname{diam}(G\,{-}\,F)=\infty$ there is nothing to show. We thus
assume that $T^{\prime}$ is connected, which implies that also $T_{F}$ is
connected. Let $i^{*}$ be an index such that
$\Delta=w^{\prime}(e_{i^{*}})-d(s,r_{i^{*}})$. We prove the lemma by showing
that the replacement distance from the source to the root $r_{i^{*}}$ observes
$d(s,r_{i^{*}},F)\geqslant w^{\prime}(e_{i^{*}})-d(s,r_{i^{*}})$. A
replacement path $P(s,r_{i^{*}},F)$ (which exists as $T_{F}$ is a connected
subgraph of $G\,{-}\,F$) crosses the cut induced by the removal of $e_{i^{*}}$
from $T_{F}$ with at least one edge, say $e=\\{x,y\\}$. Let $x$ be in the
connected component of $T_{F}\,{-}\,e_{i^{*}}$ as $r_{i^{*}}$. This implies
the following property: $d(s,r_{i^{*}},F)\geqslant d(s,y)+w(e)+d(x,r_{i^{*}})$
(0).

By 4.2, $w^{\prime}(e)\geqslant w^{\prime}(e_{i^{*}})$ as otherwise we could
replace $e_{i^{*}}$ by $e$ in $T_{F}$ and obtain a spanning tree of $G-F$
whose cost is strictly smaller than that of $T_{F}$. Moreover, by the triangle
inequality, $d(s,x)\leqslant d(s,r_{i^{*}})+d(x,r_{i^{*}})$, whence
$d(x,r_{i^{*}})-d(s,x)\geqslant-d(s,r_{i^{*}})$. Starting from B.1 and using
both inequalities, we can derive at the desired bound.

$\displaystyle d(s,r_{i^{*}},F)$ $\displaystyle\geqslant
d(s,y)+w(e)+d(x,r_{i^{*}})=d(s,y)+w(e)+d(s,x)-d(s,x)+d(x,r_{i^{*}})$
$\displaystyle=w^{\prime}(e)-d(s,x)+d(x,r_{i^{*}})\geqslant
w^{\prime}(e_{i^{*}})-d(s,x)+d(x,r_{i^{*}})$ $\displaystyle\geqslant
w^{\prime}(e_{i^{*}})-d(s,r_{i^{*}})=\Delta.$

##  Appendix C A Path-Reporting $f$-DSO with $\widetilde{O}(f\hskip
1.00006ptn^{(1-1/f)\delta})$ Query Time

Recall that we assume that any shortest path in $G-F$ for any $F$ with
$|F|\leqslant f$ has at most $n^{\delta/f}$ many edges. Also, the $f$-DSO is
never queried with a set that contains non-edges. We use a technique
introduced by Weimann and Yuster [44]. Let $k=Cfn^{\delta}\log n$ for a
sufficiently large constant $C>0$. We create a set $G_{1},\dots,G_{k}$ of
spanning subgraphs of $G$. For every $i$, $G_{i}$ is obtained by excluding any
edge in $E$ independently with probability $n^{-\delta/f}$. Combining the
results in [44] with all replacement paths having length at most
$n^{\delta/f}$ gives the following.

######  Lemma C.1 (Weimann and Yuster [44]).

With high probability, for all pairs of vertices $s,t\in V$ and sets
$F\subseteq E$ of at most $f$ edges, there exists an index $i\in[k]$ and a
replacement path $P(s,t,F)$ such that $P(s,t,F)$ is a shortest path in
$G_{i}$.

Along the same lines, we can bounds the number of graphs that exclude at least
$f^{\prime}\leqslant f$.

######  Lemma C.2.

Let $f^{\prime}\leqslant f$ be a positive integer. With high probability for
all sets $F\subseteq E$ with $f^{\prime}=|F|$, there are
$\widetilde{O}(fn^{(1-f^{\prime}/f)\delta)})$ subgraphs $G_{i}$ such that no
edge of $F$ is in $G_{i}$.

######  Proof C.3.

Let $k_{F}$ denote the number of subgraphs that exclude at least all of $F$.
We have $\operatorname{E}[k_{F}]=k\hskip
1.00006pt(n^{-\delta/f})^{f^{\prime}}=Cf\cdot n^{(1-f^{\prime}/f)\delta}\ln
n$. Let $N$ abbreviate $n^{(1-f^{\prime}/f)\delta}$. Using Chernoff bounds
(see e.g. [36]), we get that the probability of $k_{F}$ being more than double
its expectation is $\operatorname{P}[k_{e}\geqslant
2\operatorname{E}[k_{e}]\hskip
1.00006pt]\leqslant\exp(-\operatorname{E}[k_{F}]/3)=n^{-cfN/3}$. A union bound
over the $O(n^{2f^{\prime}})$ possible sets $F$ with $|F|=f^{\prime}$ gives
the lemma.

For each edge $e$, we record during construction the set $S_{e}$ of graphs
that exclude $e$. Computing APSP in all the $G_{i}$ takes time
$\widetilde{O}(fmn^{1+\delta})$ combinatorially or
$\widetilde{O}(fn^{\omega+\delta})$ algebraically. In the same time bounds, we
prepare an $k\times O(n^{2})$ table indexed by the subgraphs and pairs of
vertices, where the entry $[i,s,t]$ contains the distance $d_{G_{i}}(s,t)$.
Finally, we prepare, for each $G_{i}$, the information about its shortest
paths in the usual way of $n$ predecessor trees each.

Upon query $(s,t,F)$, $|F|\leqslant f$, we first have to identify those graphs
that contain no edge of $F$. One could cycle to all graphs and check each in
$O(f)$ time. However, we can slightly improve on that using the sets $S_{e}$.
We intersect the sets for all edges in $F$ to obtain the set
$S_{F}=\bigcap_{e\in F}S_{e}$ of precisely the indices we are looking for. The
intersection can be implemented such that it runs in time proportional to the
size of the smaller set. By C.2, the size of _all_ intermediate sets
$S_{F^{\prime}}$ with $F^{\prime}\subseteq F,|F^{\prime}|=f^{\prime}$ is
bounded by $2Cfn^{(1-f^{\prime}/f)\delta}\ln n$ w.h.p. Computing $S_{F}$ thus
takes time linear in

$\sum_{i=1}^{|F|}2Cfn^{(1-i/f)\delta}\ln n\leqslant 2Cfn^{(1-1/f)\delta}(\ln
n)\cdot\sum_{j=0}^{\infty}({n^{-\delta/f}})^{j}=\widetilde{O}(fn^{(1-1/f)\delta}),$

where the last estimate is due to $\delta>0$, whence ${n^{-\delta/f}}<1$.

We retrieve the minimum of all values stored in entries $[i,s,t]$ with $i\in
S_{F}$, again in time $\widetilde{O}(fn^{(1-|F|/f)\delta})$ w.h.p. This is the
correct replacement distance $d(s,t,F)$ w.h.p. by C.1. We return that minimum
and, in case it is finite, a shortest $s$-$t$-path $P$ in $G_{i}$ for some
index $i$ that assumes the minimum. In total, the query time is
$\widetilde{O}(f\hskip 1.00006ptn^{(1-1/f)\delta}+|P|)$.