# Approximate Distance Sensitivity Oracles in Subquadratic Space

Davide Bilò  Department of Information Engineering, Computer Science and
Mathematics, University of L’AquilaL’AquilaItaly<EMAIL_ADDRESS>,
Shiri Chechik  Department of Computer Science,
Tel Aviv UniversityTel AvivIsrael<EMAIL_ADDRESS>,  Keerti Choudhary
Department of Computer Science and Engineering, Indian Institute of Technology
DelhiNew DelhiIndia<EMAIL_ADDRESS>,  Sarel Cohen  School of Computer
Science, The Academic College of Tel Aviv-YaffoTel AvivIsrael
<EMAIL_ADDRESS>,  Tobias Friedrich  ,  Simon Krogmann  Hasso Plattner
Institute,
University of PotsdamPotsdamGermany<EMAIL_ADDRESS>and  Martin
Schirneck  Faculty of Computer Science, University of ViennaViennaAustria
<EMAIL_ADDRESS>
###### Abstract.

An _$f$ -edge fault-tolerant distance sensitive oracle_ ($f$-DSO) with stretch
$\sigma\geqslant 1$ is a data structure that preprocesses a given undirected,
unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer
$f$. When queried with a pair of vertices $s,t$ and a set $F$ of at most $f$
edges, it returns a $\sigma$-approximation of the $s$-$t$-distance in $G-F$.

We study $f$-DSOs that take subquadratic space. Thorup and Zwick [JACM 2015]
showed that this is only possible for $\sigma\geqslant 3$. We present, for any
constant $f\geqslant 1$ and $\alpha\in(0,\frac{1}{2})$, and any
$\varepsilon>0$, an $f$-DSO with stretch $3+\varepsilon$ that takes
$\widetilde{O}(n^{2-\frac{\alpha}{f+1}}/\varepsilon)\cdot O(\log
n/\varepsilon)^{f+1}$ space and has an $O(n^{\alpha}/\varepsilon^{2})$ query
time.

We also give an improved construction for graphs with diameter at most $D$.
For any constant $k$, we devise an $f$-DSO with stretch $2k-1$ that takes
$O(D^{f+o(1)}n^{1+1/k})$ space and has $\widetilde{O}(D^{o(1)})$ query time,
with a preprocessing time of $O(D^{f+o(1)}mn^{1/k})$.

Chechik, Cohen, Fiat, and Kaplan [SODA 2017] presented an $f$-DSO with stretch
$1{+}\varepsilon$ and preprocessing time $O_{\varepsilon}(n^{5+o(1)})$, albeit
with a super-quadratic space requirement. We show how to reduce their
preprocessing time to $O_{\varepsilon}(mn^{2+o(1)})$.

approximate shortest paths, distance sensitivity oracle, fault-tolerant data
structure, subquadratic space

††ccs: Theory of computation Data structures design and analysis††ccs: Theory
of computation Shortest paths††ccs: Mathematics of computing Graph algorithms

##  1\. Introduction

_Distance Oracles_ (DOs) are fundamental data structures that store
information about the distances of an input graph $G=(V,E)$.111Throughout, we
assume the graph $G$ to be undirected and unweighted. We use $n$ for the
number of vertices and $m$ for the number of edges.  These oracles are used in
several applications where one cannot afford to store the entire input, but
still wants to quickly retrieve the graph distances upon query. Therefore, DOs
should provide reasonable trade-offs between space consumption, query time,
and _stretch_ , that is, the quality of the estimated distance.

We are interested in the design of DOs that additionally can tolerate multiple
failures of edges in $G$. An _$f$ -edge fault-tolerant distance sensitivity
oracles_ ($f$-DSO) is able to report an estimate $\widehat{d}_{G-F}(s,t)$ of
the distance $d_{G-F}(s,t)$ between $s$ and $t$ in the graph $G-F$, where
$F\subseteq E$ is a set of at most $f$ failing edges, when queried with the
triple $(s,t,F)$. The parameter $f$ is the _sensitivity_ of the DSO. We say
that the _stretch_ of the $f$-DSO is $\sigma\geqslant 1$ if
$d_{G-F}(s,t)\leqslant\widehat{d}_{G-F}(s,t)\leqslant\sigma\,{\cdot}\,d_{G-F}(s,t)$
holds for every query $(s,t,F)$.

Several $f$-DSOs with different size-stretch-time trade-offs have been
proposed in the last decades, some of which can only deal with a very small
number $f\in\\{1,2\\}$ of failures (Baswana and Khanna, 2013; Bernstein and
Karger, 2008, 2009; Bilò et al., 2021a; Chechik and Cohen, 2020; Demetrescu
and Thorup, 2002; Demetrescu et al., 2008; Duan and Pettie, 2009; Grandoni and
Vassilevska Williams, 2020; Gu and Ren, 2021; Ren, 2022). In the following, we
focus on $f$-DSOs that deal with multiple failures $f\geqslant 3$. The Monte
Carlo $f$-DSO of Weimann and Yuster (2013) computes exact distances
w.h.p.222An event occurs _with high probability_ (w.h.p.) if it has
probability at least $1-n^{-c}$ for some constant $c>0$.  and gives adjustable
trade-offs depending on some parameter $\alpha\in(0,1)$. More precisely, the
$f$-DSO can be built in $\widetilde{O}(mn^{2-\alpha})$ time, has a query time
of $\widetilde{O}(n^{2-2(1-\alpha)/f})$, and uses
$\widetilde{O}(n^{3-\alpha})$ space.333The space is measured in the number of
machine words on $O(\log n)$ bits. For a function $g$ of the input and
parameters, we use $\widetilde{O}(g)$ to denote
$O(g\cdot\textsf{polylog}(n))$.  The $f$-DSO of Duan and Ren (2022) requires
$O(fn^{4})$ space, returns exact distances in $f^{O(f)}$ query time, but the
preprocessing algorithm that builds takes $n^{\Omega(f)}$ time. The $f$-DSO of
Chechik, Cohen, Fiat, and Kaplan (Chechik et al., 2017) can handle up to
$f=o(\log n/\log\log n)$ failures but has a stretch of $1+\varepsilon$, for
any constant $\varepsilon>0$. In turn, the oracle is more compact requiring
$O_{\varepsilon}(n^{2+o(1)}\log W)$ space, where $W$ is the weight of the
heaviest edge of $G$, has query time $O_{\varepsilon}(f^{5}\log n\log\log W)$,
and can be build in $O_{\varepsilon}(n^{5+o(1)}\log W)$ preprocessing time.
Note that the aforementioned $f$-DSOs all have a super-quadratic space
requirement, that is, they take up _more_ space than the original input graph,
which is prohibitive in settings where we cannot even afford to store $G$. The
$f$-DSO of Chechik, Langberg, Peleg, and Roditty (Chechik et al., 2012)
addresses this issue with a space requirement of $O(fkn^{1+1/k}\log(nW))$,
where $k\geqslant 1$ is an integer parameter. Their data structure has a fast
query time of $\widetilde{O}(|F|\log\log d_{G-F}(s,t))$ but guarantees only a
stretch of $(8k-2)(f+1)$, that is, depending on the sensitivity $f$.

Another way to provide approximate pairwise replacement distances under edge
failures is that of fault-tolerant spanners (Levcopoulos et al., 1998). An _(
$f$-edge) fault-tolerant $\sigma$-spanner_ is a subgraph $H$ of $G$ such that
$d_{H-F}(s,t)\allowbreak\leqslant\sigma\cdot d_{G-F}(s,t)$, for every triple
$(s,t,F)$, with $s,t\in V$ and $F\subseteq E$, $|F|\leqslant f$. There is a
simple algorithm by Chechik, Langberg, Peleg, and Roditty (Chechik et al.,
2010) that computes, for any positive integer $k$, a fault-tolerant
$(2k{-}1)$-spanner with $O(fn^{1+1/k})$ edges. Constructions by Bodwin,
Dinitz, and Robelle (Bodwin et al., 2021, 2022) recently reduced the size to
$f^{1/2}n^{1+1/k}\cdot\textsf{poly}(k)$ for even $k$, and
$f^{1/2-1/(2k)}n^{1+1/k}\cdot\textsf{poly}(k)$ for odd $k$. They also showed
an almost matching lower bound of $\Omega(f^{1/2-1/(2k)}n^{1+1/k}+fn)$ for
$k>2$, and $\Omega(f^{1/2}n^{3/2})$ for $k=2$, assuming the Erdős girth
conjecture (Erdős, 1964). The space is also the main problem with this
approach as it translates to a high query time. Currently, the most efficient
way to retrieve the approximate distance between a given pair of vertices is
to compute the single-source distance from one of them in time that is at
least linear in the size of the spanner.

All the results above for multiple failures either require $\Omega(n^{2})$
space, have a stretch depending on $f$, or superlinear query time. If we want
a truly constant stretch for every (constant) sensitivity $f$ and fast query
time simultaneously, one currently has to pay $\Omega(n^{2})$ space. A natural
question is whether we can break the quadratic barrier. In this paper, we
answer this question affirmatively.

###### Theorem 1.1.

Let $f\geqslant 2$ be a positive integer and $0<\alpha<\nicefrac{{1}}{{2}}$ a
constant. For any undirected, unweighted graph $G$ with unique shortest paths
and any $\varepsilon>0$, there is a $(3{+}\varepsilon)$-approximate $f$-DSO
for $G$ that takes space
$\widetilde{O}(n^{2-\frac{\alpha}{f+1}}/\varepsilon)\,{\cdot}\,O(\log
n/\varepsilon)^{f+1}$, has query time $O(n^{\alpha}/\varepsilon^{2})$, and
preprocessing time
$\widetilde{O}(n^{2-\frac{\alpha}{f+1}}(\frac{m}{\varepsilon}+\frac{1}{\varepsilon^{2}}))\cdot
O(\log n/\varepsilon)^{f}$.

The assumption of unique shortest paths in the base graph $G$ can be achieved
by perturbing the edge weights of the input. For unweighted graphs, this
results in weighted graphs where every edge weight is very close to $1$, which
is a sufficient alternative condition for all the places in the paper where we
assume that the graph is unweighted. Alternatively, we can compute a set of
unique paths via _lexicographic pertubation_ (Cabello et al., 2013) in time
$O(mn+n^{2}\log^{2}n)$. To obtain Theorem 1.1, we develop several new
techniques. For the remainder of this section, we highlight the novelties. A
more detailed overview of our construction can be found in Section 2.

Tree Sampling for Short Paths. It is a common approach in the design of fault-
tolerant data structures to first give a solution for short paths and then
combine them into one for all distances, see (Chechik and Cohen, 2020; Karthik
C.S. and Parter, 2021; Grandoni and Vassilevska Williams, 2020; Gu and Ren,
2021; Ren, 2022; Weimann and Yuster, 2013). We also focus first on $f$-DSOs
for short paths. Let $L$ be the cut-off parameter.444The cut-off point will
eventually turn out to be $L=n^{\alpha/(f+1)}$, where
$\alpha\in(0,\frac{1}{2})$ is the parameter from Theorem 1.1.  We say a path
is _short_ if it has at most $L$ edges. An $f$-DSO for short paths only needs
to report the correct answer for a query $(s,t,F)$ if $G-F$ contains a
shortest path from $s$ to $t$ with at most $L$ edges. Designing such an oracle
with good query-space-preprocessing trade-offs is the first step towards
improving general $f$-DSOs. Let $d_{G-F}^{\leqslant L}(s,t)$ be the minimum
length over all $s$-$t$-paths in $G-F$ with at most $L$ edges; if there are
none, then $d_{G-F}^{\leqslant L}(s,t)=+\infty$. Note that $d_{G-F}^{\leqslant
L}(s,t)=+\infty$ may hold for pairs $(s,t)$ that are connected in $G-F$.

###### Theorem 1.2.

Let $f,k$ be positive integers. There exists a data structure that, when given
an undirected, unweighted graph $G=(V,E)$, and a positive integer $L$
(possibly dependent $n$ and $m$), preprocesses $G$ and answers queries
$(s,t,F)$ for vertices $s,t\in V$ and sets of edges $F\subseteq E$ with
$|F|\leqslant f$. W.h.p. over all queries, the returned value
$\widehat{d^{\leqslant L}}(s,t,F)$ satisfies
$d_{G-F}(s,t)\leqslant\widehat{d^{\leqslant
L}}(s,t,F)\leqslant(2k{-}1)\,{\cdot}\,d_{G-F}^{\leqslant L}(s,t,F)$. The data
structure takes space $\widetilde{O}(L^{f+o(1)}\hskip 1.00006ptn^{1+1/k})$,
has query time $\widetilde{O}(L^{o(1)})$, and preprocessing time
$\widetilde{O}(L^{f+o(1)}\hskip 1.00006ptmn^{1/k})$.

We compare Theorem 1.2 with previous work on $f$-DSOs for short paths. Weimann
and Yuster (2013) presented a construction with $\widetilde{O}(L^{f}mn)$
preprocessing time, $\widetilde{O}(L^{f}n^{2})$ space, and
$\widetilde{O}(L^{f})$ query time. It laid the foundation for many subsequent
works, see (Alon et al., 2019; Bilò et al., 2021b, 2022; Karthik C.S. and
Parter, 2021; Ren, 2022). When using the fault-tolerant trees described in
Appendix A of (Chechik et al., 2017), one can reduce the query time of the
oracle to $O(f^{2})$. However, storing all of these fault-tolerant trees still
requires $\Omega(L^{f}n^{2})$ space. For small enough $L$, sub-quadratic space
suffices for our data structure, while still providing a better query time
than (Weimann and Yuster, 2013).

In order to prove Theorem 1.2, we extend the sampling technique by Weimann and
Yuster (2013). It consists of first constructing $\widetilde{O}(L^{f})$ copies
of $G$ and then, in each one, remove edges with probability
$\nicefrac{{1}}{{L}}$. One can show that w.h.p. each short replacement path
survives in one of the copies, where a _replacement path_ is the respective
shortest path after at most $f$ edge failures. Instead of having all those
graphs be independent of each other, we develop hierarchical tree sampling.
This allows us to quickly find the copies that are relevant for a given query,
reducing the query time to $\widetilde{O}(L^{o(1)})$. We further sparsify the
resulting graphs for a better space complexity.

From Theorem 1.2, we immediately get an $f$-DSO for graphs with bounded
diameter. Afek, Bremler-Barr, Kaplan, Cohen, and Merritt (Afek et al., 2002)
proved that for undirected, unweighted graphs $G$ any shortest path in $G-F$
is a concatenation of up to $|F|+1$ shortest paths in $G$. If $G$ has diameter
at most $D$ and $|F|\leqslant f$, the diameter of $G-F$ is thus bounded by
$(f{+}1)D$. This gives the following corollary.

###### Corollary 1.3.

Let $f$ and $k$ be positive integers. There exists a $(2k{-}1)$-approximate
$f$-DSO for undirected, unweighted graphs with diameter bounded by $D$, that
takes space $\widetilde{O}(D^{f+o(1)}\hskip 1.00006ptn^{1+1/k})$, has query
time $\widetilde{O}(D^{o(1)})$, and preprocessing time
$\widetilde{O}(D^{f+o(1)}\hskip 1.00006ptmn^{1/k})$.

Fault-Tolerant Trees with Granularity. We employ fault-tolerant trees555FT-
trees are not related to the tree sampling mentioned before.  (FT-trees)
introduced by Chechik et al. (2017) to combine the solutions for short paths.
Those are trees in which every node is associated with a path in a subgraph
$G-A$ where $A\subseteq E$ is a set of edges, but possibly much more than the
sensitivity $f$. Each path is partitioned into segments whose sizes increase
exponentially towards the middle. This is done to encode the paths more space
efficient than edge-by-edge. We have to take some additional compression steps
to fit them in subquadratic space. For example, instead of building a tree
$FT(s,t)$ for every pair of vertices $s,t$, we only do so if one of them is
from a set of randomly selected _pivots_. But even this gives only a sub-
linear query time. To improve it further to
$\widetilde{O}_{\varepsilon}(n^{\alpha})$ for an any constant
$\alpha\in(0,\frac{1}{2})$, we generalize the FT-trees by adding what we call
_granularity_ $\lambda\geqslant 0$.666In the proof of Theorem 1.1, we set
$\lambda=\varepsilon L/c$, for an ad-hoc constant $c>1$.  That means the first
and last $\lambda$ edges of each path are their own segment and do not fall
into the regime of exponential increase. The original construction in (Chechik
et al., 2017) corresponds to granularity $0$. Intuitively, the larger the
value of $\lambda$, the better the fault-tolerant tree $FT_{\lambda}(u,v)$
with granularity $\lambda$ approximates the shortest distance from $u$ to $v$
in $G-F$, but the larger the size of each node of the tree becomes.

The idea to answer a query $(s,t,F)$ is to scan balls of a certain radius
around $s$ and $t$ in $G-F$ for pivots and query the respective FT-tree
together with the oracle for short paths in Theorem 1.2. W.h.p. one of the
pivots hits the replacement path from $s$ to $t$ ensuring that this gives (an
approximation of) the right distance. The bottleneck is the case when there
are too many vertices in the vicinity of both $s$ and $t$ since then these
balls also receive many pivots. Instead, we sample a second type of much more
scarce pivots, which are used to hit the dense neighborhoods. In that case, we
can find a scarce pivot $b_{s}$ near $s$ and a scarce pivot $b_{t}$ near $t$,
but we can no longer assume that they hit the sought replacement path. The
fault-tolerant tree $FT_{\lambda}(b_{s},b_{t})$ with granularity $\lambda$,
however, allows us to get a good approximation, as long the starting points
$b_{s}$ and $b_{t}$ are at distance at most $\lambda$ from the real endpoints.

The trees $FT_{\lambda}(b_{s},b_{t})$ are much larger than their classical
counterparts $FT(s,t)$. This is compensated by the fact that we require much
fewer of those. We verify that several of the key lemmas from (Chechik et al.,
2017) transfer to fault-tolerant trees with granularity $\lambda>0$.

Efficient Computation of Expaths. Since fault-tolerant trees are crucial for
our work, we revisit the approach used by Chechik et al. (2017) to construct
them (with granularity $0$). It turns out that their algorithm can be
improved. The preprocessing in (Chechik et al., 2017) invokes many calls to
all-pairs shortest path computations (APSP) in different subgraphs $G-F$, each
of which is associated with a node of the fault-tolerant trees. They also
invoke $O(n)$ calls to Dijkstra’s algorithm on suitable dense graphs with
$O(fn^{2})$ edges. We prove that many of those APSP calls can be avoided by
instead re-using the distances in the original graph $G$, which can be
obtained by a single APSP computation. More precisely, the paths associated
with the nodes of the fault-tolerant trees (later referred as
$(2f+1)$-expaths) are the concatenation of $O(f\log(nW))$ original shortest
paths. The distances in $G$ can be integrated into a single Dijkstra run on a
specially built graph with $\widetilde{O}(fm)$ edges to compute such an expath
in time $\widetilde{O}(fm)$. This technique implies an improved preprocessing
time for our own subquadratic $f$-DSO. Moreover, when plugged in the
preprocessing algorithm in (Chechik et al., 2017), it improves the overall
time complexity from $O_{\varepsilon}(fn^{5+o(1)})$ to
$O_{\varepsilon}(fmn^{2+o(1)})$. The details of the improved expath
computation are deferred to Appendix B.

###### Theorem 1.4.

Let $G$ be an undirected weighted graph with maximum edge weight
$W=\emph{{poly}}(n)$ and unique shortest paths. For any positive integer
$f=o(\log n/\log\log n)$, and $\varepsilon\geqslant 1/nW$, there exists an
$(1{+}\varepsilon)$-approximate $f$-DSO for $G$ that takes
$\widetilde{O}(fn^{2})\cdot
O\\!\left(\frac{\log(nW)}{\varepsilon}\right)^{f}=O(\varepsilon^{-f})\cdot
n^{2+o(1)}$ space, has query time $O(f^{5}\log n)$, and preprocessing time
$\widetilde{O}(fmn^{2})\cdot
O\\!\left(\frac{\log(nW)}{\varepsilon}\right)^{f}=O(\varepsilon^{-f})\cdot
mn^{2+o(1)}$.

Open Problems. As an open question, we ask whether one can further improve the
query time from $\widetilde{O}_{\varepsilon}(n^{\alpha})$ to poly-logarithmic
in $n$ and $\nicefrac{{1}}{{\varepsilon}}$ while keeping the space truly
subquadratic. The converse open problem is to further reduce the space without
affecting the query time. Finally, we can only handle unweighted graphs
currently where the length of the path corresponds to the number of edges.
Some of the sampling-based ideas break down if long paths can consist of only
a few heavy edges. For all the open problems the bottleneck is the case of
long paths. For short path distances, we have an $f$-DSO of asymptotically
almost optimal size and very low query time that can easily be adapted to the
weighted case.

##  2\. Overview

Fault-tolerant Trees. Our distance sensitivity oracle is built on the concept
of fault-tolerant trees (Chechik et al., 2017). This is a data structure that
reports, for a fixed pair of vertices $s,t\in V$ and any set $F\subseteq E$ of
up to $f$ edge failures, the replacement distance $d_{G-F}(s,t)$. Consider a
shortest path $P$ from $s$ to $t$ in the original graph $G$. FT-trees draw
from the fact that only failures on $P$ can influence the distance from $s$ to
$t$. In its simplest form, the tree $FT(s,t)$ consists of a root node that
stores the path $P$ and the distance $d(s,t)=|P|$. It has a child for each
edge $e\in E(P)$ which in turn holds a shortest $s$-$t$-path in $G\,{-}\,e$.
Iterating this construction until depth $f$ ensures that all relevant failure
sets for the pair $(s,t)$ are covered. If some set of edge failures disconnect
the two vertices, this is represented by a leaf node that does not store any
path. Let $P_{\nu}$ denote the path in some node $\nu$. Given a failure set
$F$, the algorithm checks in each node $\nu$ starting with the root whether it
is a leaf or $F\cap E(P_{\nu})=\emptyset$, with the latter meaning that the
path $P_{\nu}$ exists in $G-F$. If so, its length $|P_{\nu}|$ is reported;
otherwise, the search recurses on the child node corresponding to an
(arbitrary) edge $e\in F\cap E(P_{\nu})$. Let $FT(s,t,F)$ be the reported
distance. It is equal to $d_{G-F}(s,t)$ and the query time is $O(f^{2})$ since
at most $f{+}1$ vertices are visited and computing the intersection takes time
$O(f)$.

The problem is, these trees are huge. Preprocessing them for all pairs of
vertices takes total space $O(n^{f+3})$. The main technical contribution of
(Chechik et al., 2017) is to reduce the space without sacrificing too much of
their performance, that is, the stretch of the reported distance and the query
time. In the first step, the number of vertices in the tree is decreased by
introducing an approximation parameter $\varepsilon>0$. Each path $P_{\nu}$ is
split into $O(\log n/\varepsilon)$ _segments_. Now node $\nu$ only has a child
for each segment and the search procedure recursing on that child corresponds
to failing the whole segment instead of only a single edge. This reduces the
total size of all trees to $O(n^{3}\,(c\hskip 1.00006pt\frac{\log
n}{\varepsilon})^{f})$ for some constant $c>0$. However, it leads to some
inaccuracies in the answer of the tree. The failed segments may contain edges
that are actually present in $G-F$ and thus the path $P_{\nu^{*}}$ stored in
the last visited node $\nu^{*}$ may take unnecessary detours. It is proven in
(Chechik et al., 2017) that $FT(s,t,F)=|P_{\nu^{*}}|=d_{G-F}(s,t)$ is correct
if all failing edges are “far away”777More formally, a path $P$ being “far
away” from $F$ means that, for every vertex $x$ on $P$ except for $s$ and $t$
and every endpoint $y$ of a failing edge in $F$, the distance from $x$ to $y$
is more than $\frac{\varepsilon}{9}\cdot\min(\hskip
1.00006pt|P[s,x]|,\,|P[x,t]|\hskip 1.00006pt)$, see Definition 5.2.  from the
true replacement path $P(s,t,F)$ in $G-F$, where the required safety distance
depends on the distance $d_{G-F}(s,t)$. To also answer queries for which this
condition is violated, they consult multiple FT-trees. An auxiliary graph
$H^{F}$ is constructed on the endpoints $V(F)$ of all failing edges, that is,
$V(H^{F})=\\{s,t\\}\cup V(F)$. For each pair of vertices $u,v\in V(H^{F})$,
the edge $\\{u,v\\}$ is weighted with the reported distance $FT(u,v,F)$. While
not all edge weights may be the correct $u$-$v$-replacement distance, the
distance of $s$ and $t$ in $H^{F}$ can be shown to be a
$(1{+}\varepsilon)$-approximation of $d_{G-F}(s,t)$. The idea is that, when
going from $s$ to $t$, one can always find a next vertex in $V(H^{F})$ that is
not too far off the shortest path and such that the subpath to that vertex is
“far away” from all failures. Computing the weights for $H^{F}$ increases the
query time to $O(f^{4})$.

The next step is more involved and is concerned with the size of the nodes in
the FT-trees. Originally, each of them stores all edges of a path in (a
subgraph of) $G$ and therefore may take $O(n)$ space. Afek et al. (2002)
showed that every shortest path in $G{-}F$, for $|F|\leqslant f$, is
$f$-_decomposable_ , that is, a concatenation of at most $f$ shortest paths in
$G$. Chechik et al. (2017) extend this notion to so-called expaths. For a
positive integer $\ell$, a path is said to be an $\ell$-_expath_ if it is the
concatenation of $(2\log_{2}(n)+1)$ $\ell$-decomposable paths such that the
$i$th $\ell$-decomposable path has length at most
$\min\\{2^{i},2^{2\log_{2}(n)-i}\\}$. Consider a node $\nu$ in the tree
$FT(u,v)$. Instead of storing the shortest $u$-$v$-path $P_{\nu}$ edge by
edge, one would like to represent it by the endpoints of the constituting
shortest paths (in $G$) and edges. However, the collection $A_{\nu}$ of edges
in all segments that were failed while descending from the root to $\nu$ may
be much larger than $f$ and $P_{\nu}$ may not be $f$-decomposable. Instead,
the node $\nu$ now holds the shortest $(2f{+}1)$-expath from $u$ to $v$ in
$G-A_{\nu}$. It can be represented by $O(f\log n)$ endpoints, bringing the
total space of the trees to $O(fn^{2}(\log n)(c\hskip 1.00006pt\frac{\log
n}{\varepsilon})^{f})$. It is described in (Chechik et al., 2017) how to
navigate the new representation to obtain a $(1{+}\varepsilon)$-approximation
of $d_{G-F}(s,t)$ in time $O(f^{5}\log n)$.

In this work, we advance the space reduction further into the subquadratic
regime. Recall that $L$ is the number of edges up to which a path is called
short. When sampling a set $B$ of $\widetilde{O}_{\varepsilon}(n/L)$ _pivots_
uniformly at random, then w.h.p. every long replacement path contains a pivot.
Restricting the FT-trees $FT(u,v)$ to only those pairs $u,v$ for which at
least one vertex is in $B$ brings the total number of trees to $o(n^{2})$.
Unfortunately, it deprives us of the replacement distances for pairs that are
joined by a short path.

Short Paths. To make up for this deficit, we design an approximate $f$-DSO for
vertex pairs with short replacement paths. We extend a technique by Weimann
and Yuster (2013) from exact to approximate distances while also reducing the
required space and query time. When sampling $\widetilde{O}(L^{f})$ spanning
subgraphs of $G$ by, in each one, removing any edge independently with
probability $\nicefrac{{1}}{{L}}$, it is shown in (Weimann and Yuster, 2013)
that w.h.p. for each set $F$ of at most $f$ edges and each pair of vertices
connected by a short path in $G-F$, there are $\widetilde{O}(1)$ subgraphs
that contain the path but none of $F$. Such a collection of graphs is called
an $(L,f)$-_replacement path covering_ (RPC) (Karthik C.S. and Parter, 2021).
For any two vertices $s$ and $t$ that have a replacement path on at most $L$
edges, the minimum $s$-$t$-distance of the $\widetilde{O}(1)$ suitable graphs
of the RPC is the correct replacement distance.

We cannot use that approach directly in subquadratic space. The subgraphs have
total size $\Omega(L^{f}m)$, which is already too large if $G$ is dense. Also,
it is expensive to find the correct members of the RPC for a given query. In
(Weimann and Yuster, 2013), the solution was to go over all graphs and
explicitly check whether they have the set $F$ removed, dominating the query
time (for short paths). Karthik and Parter (Karthik C.S. and Parter, 2021)
derandomized this construction and thereby reduced the time needed to find the
correct subgraphs to $\widetilde{O}(L)$. Both approaches break down in
subquadratic space, since we cannot even store all edges of the graphs.
However, we are only seeking _approximate_ replacement distances. We exploit
this fact in a new way of constructing and approximate $(L,f)$-replacement
path coverings. We do so by turning the sampling technique upside down and
combining it with the distance oracle of Thorup and Zwick (2005).

Instead of sampling the subgraphs directly by removing edges, we construct
them in a hierarchical manner by _adding_ connections. We build a
tree888Again, sampling trees and fault-tolerant trees are not related.  in
which each node is associated with a subset of the edges of $G$, this set
stands for the “missing” edges. We start with the full edge set $E$ in the
root, that is, the graph in the root is empty. The height of the tree is $h$
and each node has $L^{f/h}$ children. The associated set of a child node
contains any edge of its parent with probability $L^{-1/h}$. This corresponds
to adding any missing edge with probability $1-L^{-1/h}$. Knowing the missing
edges upfront benefits the query algorithm. At each node starting with the
root, if we were to expand all children in which all failures of $F$ are
missing, we would find the suitable subgraphs. The hierarchical sampling
creates some dependencies among the subgraphs associated with the leaves of
the tree, while the graphs in (Weimann and Yuster, 2013) were independent. We
tackle this issue by always recursing only on one child node and therefore
querying a single leaf. We repeat the process in several independent trees in
order to amplify the success probability. We prove that there exists a
constant $c>0$ such that $\widetilde{O}(c^{h})$ trees together ensure the
property we need from an $(L,f)$-replacement path covering w.h.p. Optimizing
the height $h$ gives an $\widetilde{O}(L^{o(1)})$ query time (assuming
constant $f$).

The main challenge is to bring down the size of this construction by reducing
the number of edges in the graphs associated with the nodes of the trees.
Thorup and Zwick (2005) devised, for any positive integer $k$, a
$(2k{-}1)$-approximate distance oracle together with a compatible spanner of
size $O(kn^{1+1/k})$, i.e., the stretched distance returned by the oracle is
the length of a shortest path in the spanner. Therefore, we can use the
oracles in the leaves of the trees to report distances, giving a low query
time, and employ the spanners as proxies for the graphs associated with the
intermediate nodes. However, for this to work, we have to carefully tweak the
computation of the spanners and interleave it with the sampling process in
order to not blow up the size too much (or the stretch).

Long Paths. We return to the fault-tolerant trees. By the use of the pivots,
we reduced the required number of trees to
$\widetilde{O}_{\varepsilon}(n^{2}/L)$. But even in the most compact version
of FT-trees, this is not enough to reach subquadratic space altogether. The
issue is with the representation of expaths as a sequence of $O(f\log n)$
components, each of which is implicitly represented by its two endpoints. In
(Chechik et al., 2017) this was implemented by storing the original graph
distance $d(x,y)$ and the predecessor $\operatorname{pred}(x,y)$ of $y$ on the
shortest $x$-$y$-path for _all_ pairs $x,y$. This information is used to
expand the implicit representation of an expath when needed. However, the
space is again $\Omega(n^{2})$. The key observation to overcome this is that,
in our case, we do not need to encode arbitrary expaths but only those with a
particular structure, e.g., at least one endpoint is a pivot. This allows us
to forgo the need for a quadratic database of all distances.

We also devise a new procedure to obtain an approximation of $d_{G-F}(s,t)$ by
combining the values from the FT-trees with the $f$-DSO for short paths.
Recall that we build one FT-tree for each pair of vertices $(u,v)$ where $u$
or $v$ are pivots. The main open issue is to find the weight of the edge
$\\{u,v\\}$ in the auxiliary graph $H^{F}$ (see above) if neither $u$ nor $v$
are pivots and they also do not have a short path between them in $G-F$. Then,
w.h.p. at least one pivot $b$ hits the $L$-edge prefix of that replacement
path. Therefore, it is sufficient to estimate its length as the sum of an
approximation for $d_{G-F}^{\leqslant L}(u,b)$ via the $f$-DSO for short
paths, and an approximation for $d_{G-F}(b,v)$ via the FT-trees. However,
since we do not know the right pivot $b$, we have to scan all of them. We
prove that this results in a stretch of $3+\varepsilon$ and a sublinear query
time.

While this is already faster than all previous works (for a stretch
independent of $f$), it is still not very efficient. In Section 6, we improve
the query time to $O_{\varepsilon}(n^{\alpha})$ for any constant
$0<\alpha<1/2$. We provide an efficient way to check whether the number of
pivots in $B$ that are close to $u$ and $v$ in $G-F$ are below the threshold
value of $L^{f-1}$ and, if so, find them all. If only a small number of pivots
are around $u$ (or $v$), we can afford to scan them as described above.

The complementary case of many pivots around both endpoints is solved by
precomputing a set of $\widetilde{O}_{\varepsilon}(n/L^{f})$ _new pivots_ ,
much fewer than before, and generalizing the FT-trees to granularity
$\lambda>0$. This ensures that, in any node $\nu$, the first and last
$\lambda$ edges of the corresponding path $P_{\nu}$ each form their own
segment. High granularity thus makes the generalized trees much larger. For
comparison, the maximum granularity $\lambda=n$ would unwind _all_ of the
efforts taken in (Chechik et al., 2017) to reduce their size, as summarized at
the beginning of this section. We can still fit the trees in subquadratic
space by building $FT_{\lambda}(b,b^{\prime})$ only for pairs $b,b^{\prime}$
of new pivots.

The $u$-$v$-distance in $G-F$ in the case of many _original_ pivots around $u$
and $v$ is approximated as follows. We compute two _new_ pivots $b_{u},b_{v}$,
with $b_{u}$ close to $u$ in $G-F$ and $b_{v}$ close to $v$. The approximate
length of the shortest path from $u$ to $v$ in $G-F$ is computed by the
overall sum of (i) an approximation of the distance from $u$ to $b_{u}$ in
$G-F$, (ii) an approximation of the distance from $b_{u}$ to $b_{v}$ in $G-F$
computed by visiting $FT_{\lambda}(b_{u},b_{v})$, and (iii) an approximation
of the distance from $b_{v}$ to $v$ in $G-F$. We make sure to have a
granularity $\lambda\leqslant L$ so as to compute the approximations (i) and
(iii) using our $f$-DSO for short paths.

##  3\. Preliminaries

We let $G=(V,E)$ denote the undirected and unweighted base graph with $n$
vertices and $m$ edges. We tacitly assume $m=\Omega(n)$. For any undirected
(multi-)graph $H$, which may differ from the input $G$, we denote by $V(H)$
and $E(H)$ the set of its vertices and edges, respectively. Let $P$ be a path
in $H$ from a vertex $s\in V(H)$ to $t\in V(H)$, we say that $P$ is an _$s$
-$t$-path_ in $H$. We denote by $|P|=|E(P)|$ the _length_ of $P$. For vertices
$u,v\in V(P)$, we let $P[u..v]$ denote the subpath of $P$ from $u$ to $v$. Let
$P=(u_{1},\dots,u_{i})$ and $Q=(v_{1},\dots,v_{j})$ be two paths in $H$. Their
_concatenation_ is $P\circ Q=(u_{1},\dots,u_{i},v_{1},\dots,v_{j})$, which is
well-defined if $u_{i}=v_{1}$ or $\\{u_{i},v_{1}\\}\in E(H)$. For $s,t\in
V(H)$, the _distance_ $d_{H}(s,t)$ is the minimum length of any $s$-$t$-path
in $H$; if $s$ and $t$ are disconnected, we set $d_{H}(s,t)=+\infty$. When
talking about the base graph $G$, we drop the subscripts.

A _spanning_ subgraph of a graph $H$ is one with the same vertex set as $H$
but possibly any subset of its edges. This should not be confused with a
spanner. A _spanner of stretch_ $\sigma\geqslant 1$, or _$\sigma$ -spanner_,
is a spanning subgraph $S\subseteq H$ such that additionally for any two
vertices $s,t\in V(S)=V(H)$, it holds that $d_{H}(s,t)\leqslant
d_{S}(s,t)\leqslant\sigma\cdot d_{H}(s,t)$. A _distance oracle_ (DO) for $H$
is a data structure that reports, upon query $(s,t)$, the distance
$d_{H}(s,t)$. It has _stretch_ $\sigma\geqslant 1$, or is
$\sigma$_-approximate_ , if the reported value $\widehat{d}(s,t)$ satisfies
$d_{H}(s,t)\leqslant\widehat{d}(s,t)\leqslant\sigma\cdot d_{H}(s,t)$ for any
admissible query.

For a set $F\subseteq E$ of edges, let $G{-}F$ be the graph obtained from $G$
by removing all edges in $F$. For any two $s,t\in V$, a _replacement path_
$P(s,t,F)$ is a shortest path from $s$ to $t$ in $G{-}F$. Its length
$d_{G-F}(s,t)$ is the _replacement distance_. Let $L$ be a positive integer.
We call a path in (a subgraph of) $G$ _short_ if it has at most $L$ edges, and
_long_ otherwise. Let $d_{G-F}^{\leqslant L}(s,t)$ be the minimum length of
any short $s$-$t$-paths in $G-F$, or $+\infty$ if no such path exists.

For a positive integer $f$, an _$f$ -distance sensitivity oracle_ (DSO)
answers queries $(s,t,F)$ with $|F|\leqslant f$ with the replacement distance
$d_{G-F}(s,t)$. The stretch of a DSO is defined as for DOs. The maximum number
$f$ of supported failures is called the _sensitivity_. We measure the space
complexity of any data structure in the number of $O(\log n)$-bit machine
words. The size of the input graph $G$ does not count against the space,
unless it is stored explicitly.

##  4\. Handling Short Paths

We develop here our $(2k{-}1)$-approximate solution for short replacement
paths, which will in turn be used for the general distance sensitivity oracle.
To do so, we first review (and slightly modify) the distance oracle and
spanner in (Thorup and Zwick, 2005) to an extent that is needed to present our
construction.

###  4.1. The Distance Oracle and Spanner of
Thorup and Zwick

For any positive integer $k$,999In principle, $k$ could depend on $n$ or $m$,
but for $k=\Omega(\log n)$ we do not get further space improvements. We assume
$k$ to be a constant in this work.  Thorup and Zwick (2005) devised a DO that
is computable in time $\widetilde{O}(kmn^{1/k})$, has size $O(kn^{1+1/k})$,
query time $O(k)$, and a stretch of $2k-1$. We first review their construction
before discussing our changes. First, a family of vertex subsets
$V=X_{0}\supseteq X_{1}\supseteq\cdots\supseteq X_{k-1}\supseteq
X_{k}=\emptyset$ is computed. Each $X_{i}$ is obtained by sampling the
elements of $X_{i-1}$ independently with probability $n^{-1/k}$. We keep this
family fixed and apply the construction to a variety of subgraphs of $G$.

1 $w\leftarrow s$;

2 $i\leftarrow 0$;

3 while  _$w\notin\bigcup_{j=0}^{k-1}X_{j,H}(t)$_ do

4 $i\leftarrow i+1$;

5 $(s,t)\leftarrow(t,s)$;

6 $w\leftarrow p_{i,H}(s)$;

7

8return $d_{H}(s,w)+d_{H}(w,t)$;

Algorithm 1 Original query algorithm of the distance oracle for pair $(s,t)$.

Let $H$ be such a subgraph for which the oracle needs to be computed. For any
$v\in V$ and $0\leqslant i<k$, let $p_{i,H}(v)$ be the closest vertex101010We
have $p_{i,H}(v)=v$ for all $i$ small enough so that $X_{i}$ still contains
$v$.  to $v$ in $X_{i}$ in the graph $H$, ties are broken in favor of the
vertex with smaller label. The distances from $v$ to all elements in
$X_{i,H}(v)=\\{x\in X_{i}\mid d_{H}(v,x)<\min_{y\in
X_{i+1}}d_{H}(v,y)\\}\cup\\{p_{i,H}(v)\\}$ are stored in a hash table. In
other words, $X_{i,H}(v)$ contains those vertices of $X_{i}{\setminus}X_{i+1}$
that are closer to $v$ then any vertex of $X_{i+1}$. Note that the set
$X_{i,H}(v)$ and vertices $p_{i,H}(v)$ may differ for the various subgraphs of
$G$. This completes the construction of the DO for $H$.

The oracle is accompanied by a $(2k{-}1)$-spanner with $O(kn^{1+1/k})$ edges.
It stores all those edges of $H$ that lie on a shortest path between $v$ and a
vertex in $\bigcup_{0\leqslant i<k}X_{i,H}(v)$, again ties between shortest
paths are broken using the edge labels.

Algorithm 1 shows how the oracle handles the query $(s,t)$. The returned
distance can be shown to overestimate $d_{H}(s,t)$ by at most a factor
$2k{-}1$. We instead use a slightly modified version as presented in Algorithm
2. Observe that the estimate $\widehat{d}$ produced by our version is at most
the value returned by the original one and at least the actual distance
between $s$ and $t$. Further, as before, for any $s$ and $t$, the path
corresponding to the new estimate is a concatenation of at most two original
shortest paths in $H$. The interconnecting vertex is either $p_{i,H}(s)$ or
$p_{i,H}(t)$ for some $i$, we denote it as $u_{s,t,H}$, and the
$(2k{-}1)$-approximate shortest path as $P_{s,t,H}$. The reason why we adapt
the query algorithm is a crucial inheritance property.

1 $\widehat{d}\leftarrow\infty$;

2 for  _$i=0$ to $k-1$_ do

3 if  _$p_{i}(s)\in\bigcup_{j=0}^{k-1}X_{i,H}(t)$_ then

4 $\widehat{d}\leftarrow\min\\!\big{\\{}\hskip 1.00006pt\widehat{d},\
d_{H}(s,p_{i}(s))+d_{H}(p_{i}(s),t)\big{\\}}$

5 if  _$p_{i}(t)\in\bigcup_{j=0}^{k-1}X_{i,H}(s)$_ then

6 $\widehat{d}\leftarrow\min\\!\big{\\{}\hskip 1.00006pt\widehat{d},\
d_{H}(t,p_{i}(t))+d_{H}(p_{i}(t),s)\big{\\}}$

7

8return $\widehat{d}$;

Algorithm 2 Modified query algorithm of the distance oracle for pair $(s,t)$.

###### Lemma 4.1 (Inheritance property).

Let $H\subseteq G^{\prime}\subseteq G$ be two spanning subgraphs of $G$,
$s,t\in V$ two vertices, and $P_{s,t,G^{\prime}}$ the approximate shortest
path underlying the value returned by the (modified) distance oracle for
$G^{\prime}$. If $P_{s,t,G^{\prime}}$ also exists in $H$, then
$P_{s,t,H}=P_{s,t,G^{\prime}}$, Moreover, the oracle for $H$ returns
$|P_{s,t,G^{\prime}}|$ upon query $(s,t)$.

###### Proof.

Recall that $P_{s,t,G^{\prime}}$ is a concatenation of two shortest paths in
$G^{\prime}$, say, $P(s,u)$ and $P(u,t)$, where $u=u_{s,t,G^{\prime}}$ is the
interconnecting vertex in $\bigcup_{j<k}X_{j,G^{\prime}}(s)\hskip
1.00006pt\cup\hskip 1.00006pt\bigcup_{j<k}X_{j,G^{\prime}}(t)$ that minimizes
the sum of distances $d_{G^{\prime}}(s,u)+d_{G^{\prime}}(u,t)$. Without
loosing generality, we have $u=p_{i,G^{\prime}}(s)$ for some $0\leqslant i<k$;
otherwise, we swap the roles of $s$ and $t$. Let $0\leqslant j<k$ be such that
$u\in X_{j,G^{\prime}}(t)$.

For any spanning subgraph $H\subseteq G^{\prime}$ that contains the path
$P_{s,t,G^{\prime}}$, it holds that $u=p_{i,H}(s)$ and $u\in X_{j,H}(t)$.
Here, we use that the tie-breaking for the $p_{i,H}(s)$ does not depend on the
edge set of $H$. Moreover, the shortest $s$-$u$-path and $u$-$t$-path in the
spanner for $H$ are the same as in $G$, that is, $P(s,u)$ and $P(u,t)$. As a
result, we have $u=u_{s,t,H}$ and $P_{s,t,G^{\prime}}=P_{s,t,H}$. The second
assertion of the lemma follows from $d_{H}(s,u)=|P(s,u)|$ and
$d_{H}(u,t)=|P(u,t)|$. ∎

###  4.2. Tree Sampling

We present our fault-tolerant oracle construction for short paths. Recall that
a path in $G$ is short if it has at most $L$ edges, and that
$d_{G-F}^{\leqslant L}(s,t)$ is the minimum distance over short $s$-$t$-paths
in $G-F$. Note that, while we assume $f$ and $k$ to be constants, $L$ may
depend on $m$ and $n$. We prove Theorem 1.2 in the remainder of the section.

We first compute the vertex sets $X_{0},\dots,X_{k}$. Define $h=\sqrt{f\ln
L}$, $K=\big{\lceil}((2k{-}1)L)^{{f}/{h}}\big{\rceil}$, $p=K^{-1/f}$, and
$I=C\cdot 11^{h}\ln n$ for some sufficiently large constant $C>0$ (independent
of $f$ and $k$). We build $I$ rooted trees $T_{1},\dots,T_{I}$, each of height
$h$, such that any internal node has $K$ children. For the following
description, we fix some tree $T_{i}$ and use $x$ to denote a node in $T_{i}$.
Let $y$ be the parent of $x$ in case $x$ is not the root. We associate with
each $x$ a subset of edges $A_{x}\subseteq E$ and a spanning subgraph
$S_{x}\subseteq G$ in recursive fashion. For the root of $T_{i}$, set
$A_{x}=E$; otherwise $A_{x}$ is obtained by selecting each edge of $A_{y}$
independently with probability $p$. The random choices here and everywhere
else are made independently of all other choices.

Let $r$ be the depth of $x$ in $T_{i}$ (where the root has depth $r=0$).
Define $J_{r}=4\cdot K^{h-r}$ for $r<h$, and $J_{h}=1$. The graph $S_{x}$ is
constructed in $J_{r}$ rounds. In each round, we sample a subset $A\subseteq
A_{x}$ by independently selecting each edge with probability $p^{h-r}$. We
then compute the Thorup-Zwick spanner of $S_{y}\,{-}\,A$ using the family
$X_{0},\dots,X_{k}$. Slightly abusing notation, if $x$ is the root, we define
$S_{y}=G$ here. We set $S_{x}$ to be the union of all those spanners. Note
that, for a leaf $x$ at depth $r=h$, then $A=A_{x}$ with probability $1$, so
indeed only $J_{h}=1$ iteration is needed.

For each node, we store a dictionary of the edge set $E(S_{x})$ and (except
for the root) $A_{x}\cap E(S_{y})$. We use the static dictionary construction
of Hagerup, Bro Miltersen, and Pagh (Hagerup et al., 2001) that, for a set
$M$, has space $O(|M|)$, preprocessing time $\widetilde{O}(|M|)$, and query
time $O(1)$. For each leaf of a tree, we store the (modified) distance oracle
$D_{x}$. At depth $0\leqslant r\leqslant h$, the tree $T_{i}$ has $K^{r}$
nodes. The largest dictionary at depth $r$ is the one for $A_{x}\cap E(S_{y})$
of size $O(J_{r-1}\cdot kn^{1+1/k})=O(K^{h-r+1}\hskip 1.00006ptn^{1+1/k})$
(using that $k$ is constant). Due to $K=O((2k{-}1)^{f/h}L^{f/h})$ and
$h=\sqrt{f\ln n}$, we have $K^{h+1}=O(L^{f+o(1)})$ (using that $f$ is constant
as well). In total, our data structure requires $O(I\cdot h\cdot K^{h+1}\hskip
1.00006ptn^{1+1/k})=\widetilde{O}(L^{f+o(1)}\hskip 1.00006ptn^{1+1/k})$ space
and can be preprocessed in time $O(I\cdot h\cdot
K^{h+1}(kmn^{1/k}+kn^{1+1/k}))=\widetilde{O}(L^{f+o(1)}\hskip
1.00006ptmn^{1/k})$.

###  4.3. Query Algorithm

1 $\widehat{d}\leftarrow\infty$;

2 for  _$i=1$ to $I$_ do

3 $y\leftarrow$ root of $T_{i}$;

4 while  _$y$ is not leaf_ do

5 foreach  _child $x$ of $y$_ do

6 if  _$F\cap E(S_{y})\subseteq A_{x}$_ then

7 $y\leftarrow x$;

8 continue while-loop;

9

10

11 break while-loop;

12

13 if  _$y$ is leaf_ then $\widehat{d}\leftarrow\min\\!\big{\\{}\hskip
1.00006pt\widehat{d},\ D_{y}(s,t)\big{\\}}$;

14

15return $\widehat{d}$;

Algorithm 3 Algorithm to answer query $(s,t,F)$. $D_{y}$ is the distance
oracle associated with the leaf $y$.

Algorithm 3 presents the query algorithm to report approximate distances. Fix
a query $(s,t,F)$ where $s,t\in V$ are two vertices and $F\subseteq E$ is a
set of at most $f$ edges. For each of the $I$ trees, we start at the root and
recurse on an arbitrary child, computed in the inner for-loop, that satisfies
$F\cap E(S_{y})\subseteq A_{x}$, where $y$ is parent of $x$. Note that the set
$A_{x}$ is not stored as it may be too large. (We have $|A_{x}|=m$ in the
root.) The test is equivalent to $F\cap E(S_{y})\subseteq A_{x}\cap E(S_{y})$
and can be performed in time $O(f)$ using the stored dictionaries. If at some
point no child satisfies the condition, the algorithm resumes with the next
tree. Once a leaf $y$ is reached, we query the associated (modified) distance
oracle $D_{y}$ with the pair $(s,t)$. Finally, the algorithm returns the
minimum of all oracle answers. The query time is $I\cdot
O(fhK+k)=\widetilde{O}(L^{o(1)})$.

We are left to prove correctness. That means, we claim that w.h.p. the
returned estimate is at least as large as the replacement distance $d(s,t,F)$
and, if $s$ and $t$ are joined by a short path in $G\,{-}\,F$, then this
estimate is also at most $(2k{-}1)\hskip 1.00006ptd_{G-F}^{\leqslant L}(s,t)$.
Consider the Thorup-Zwick spanner for $G-F$ and in it the approximate shortest
path $P_{s,t,G-F}$ (as defined ahead of Lemma 4.1). If $s$ and $t$ have a
short path in $G-F$, then $P_{s,t,G-F}$ has at most $(2k{-}1)L$ edges.

Let $x$ be a node at depth $r$ in the tree $T_{i}$ and let $S_{y}$ be the
spanner associated to its parent (or $S_{y}=G$ if $x$ is the root). We say $x$
is _well-behaved_ if it satisfies the following three properties.

  1. (1)

$F\cap E(S_{y})\subseteq A_{x}$.

  2. (2)

Either $x$ is a root or $|E(P_{s,t,G-F})\cap A_{x}|<K^{\frac{h-r}{f}}$.

  3. (3)

The path $P_{s,t,G-F}$ is contained in $S_{x}$.

Our query algorithm follows a path from the root to a leaf node such that at
each node Item 1 is satisfied. We show in the following lemma that any child
$x$ of a well-behaved node $y$ that fulfills Item 1 is itself well-behaved
with constant probability.

###### Lemma 4.2.

The following statements hold for any non-leaf node $y$ in the tree $T_{i}$.

  1. (i)

If $y$ satisfies Item 1, then with probability at least $1-\frac{1}{e}$ there
exists a child of $y$ that satisfies Item 1.

  2. (ii)

If $y$ satisfies Item 2, then any child of $y$ satisfies Item 2 with
probability at least $\frac{1}{4}$.

  3. (iii)

If $y$ is well-behaved and a child $x$ of $y$ satisfies Items 1 and 2, then
the probability of $x$ being well-behaved is at least $1-\frac{1}{e}$.

The root of $T_{i}$ is well-behaved with probability at least $1-\frac{1}{e}$.

The next lemma shows that the distance oracle computed for a well-behaved leaf
reports a $(2k{-}1)$-approximation of the distance in $G-F$ for short paths.

###### Lemma 4.3.

Let $s,t\in V$ be two vertices and $F\subseteq E$ a set of at most $f$ edges.
Let further $x$ be a leaf in $T_{i}$ and $D_{x}$ be the (modified) distance
oracle associated with $x$. If $x$ satisfies Item 1 with respect to $F$, then
$D_{x}(s,t)\geqslant d(s,t,F)$. Moreover, if $x$ is well-behaved with respect
to the approximate shortest path $P_{s,t,G-F}$, then
$D_{x}(s,t)\leqslant(2k{-}1)\,d(s,t,F)$.

###### Proof.

As $x$ is a leaf node, $S_{x}$ is the spanner of the graph $S_{y}-A_{x}$ and
$D_{x}$ reports the distances in $S_{x}$. By Item 1, we have $F\cap
E(S_{y})\subseteq A_{x}$ whence $S_{x}\subseteq S_{y}-A_{x}\subseteq G-F$.
This implies that $D_{x}(s,t)=d_{S_{x}}(s,t)\geqslant d_{G-F}(s,t)=d(s,t,F)$.
If $x$ is even well-behaved then, by Item 3, the path $P_{s,t,G-F}$ lies in
$S_{x}$ and thus by inheritance,
$D_{x}(s,t)\leqslant|P_{s,t,G-F}|\leqslant(2k{-}1)\cdot d(s,t,F)$. ∎

Our algorithm only ever queries leaves that fulfill Item 1, it therefore never
underestimates the distance $d(s,t,F)$. Now additionally assume that $s$ and
$t$ are connected in $G-F$ via a path with at most $L$ edges. To complete the
proof of Theorem 1.2, we need to show that, under this condition and with high
probability over all queries, our algorithm queries at least one well-behaved
leaf. If there is a short $s$-$t$-path in $G-F$ then $P_{s,t,G-F}$ has at most
$(2k-1)L$ edges. Lemma 4.2 shows that the root of each tree $T_{i}$, for
$1\leqslant i\leqslant I$, is well-behaved with probability $1-\frac{1}{e}$,
and that in each stage the query algorithm finds a well-behaved child node
with constant probability. More precisely, we arrive at a well-behaved leaf
with probability at least
$(1-\tfrac{1}{e})\cdot\Big{(}(1-\tfrac{1}{e})^{2}\hskip
1.00006pt\tfrac{1}{4}\Big{)}^{h}\geqslant\tfrac{1}{2}\cdot 11^{-h}$. Since
there are $I=c\cdot 11^{h}\ln n$ independent trees, the query algorithms fails
for any fixed query with probability at most $(1-\frac{1}{2\cdot
11^{h}})^{I}\leqslant n^{-c/2}$. We choose the constant $c>0$ large enough to
ensure a high success probability over all $O(n^{2}m^{f})=O(n^{2+2f})$
possible queries.

##  5\. Sublinear Query Time for Long Paths

Let $0<\alpha<1/2$ be a constant, where the approximation parameter
$\varepsilon>0$ may depend on $m$ and $n$. As a warm-up, we construct a
distance sensitivity oracle with the same stretch and space as in Theorem 1.1,
but only a sublinear query time of the form
$O_{\varepsilon}(n^{1-g(\alpha,f)})$, for some function $g$. In Section 6, we
then show how to reduce the query time to
$\widetilde{O}_{\varepsilon}(n^{\alpha})$. The intermediate solution serves to
highlight many of the key ideas needed to implement the classical FT-trees in
subquadratic space, but does not yet involve the granularity $\lambda$. Recall
that we assume that, for every two vertices $u$ and $v$ of $G$, there is a
unique shortest path from $u$ to $v$ in $G$. Since the short replacement paths
are handled by Theorem 1.2, we focus on long paths. The structure of this
section is as follows. We first describe the interface of an abstract data
structure _FT_ and show how to use it to get a
$(3{+}\varepsilon)$-approximation of the replacement distances. We then
implement _FT_ using FT-trees.

###### Lemma 5.1.

Let $f$ be a positive integer and $0<\alpha<1/2$ a constant. For any
undirected, unweighted graph with unique shortest paths and any
$\varepsilon>0$, there exists a $(3{+}\varepsilon)$-approximate $f$-DSO that
takes space $\widetilde{O}(n^{2-\alpha/(f+1)})\cdot O(\log
n/\varepsilon)^{f+1}$, has query time
$n^{1-\frac{\alpha}{f+1}+o(1)}/\varepsilon$, and preprocessing time
$\widetilde{O}(n^{2-\alpha/(f+1)}(m+1/\varepsilon))\cdot O(\log
n/\varepsilon)^{f}$.

###  5.1. Trapezoids and Expaths

For the interface of _FT_ , we need a bit of terminology from the work by
Chechik et al. (2017). Recall the high-level description of the original FT-
trees in Section 2. We now make precise what we mean by all failures in $F$
being “far away” from a given path. Let $0<\varepsilon<3$; moreover, it is
bounded away from $3$ ($\varepsilon$ may depend on the input). We use $V(F)$
for the set of endpoints of failing edges.

###### Definition 5.2 ($\frac{\varepsilon}{9}$-trapezoid).

Let $F\subseteq E$ a set of edges, $u,v\in V$, and $P$ a $u$-$v$-path in
$G-F$. The $\frac{\varepsilon}{9}$_-trapezoid_ around $P$ in $G-F$ is

$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)=\big{\\{}\hskip 1.00006ptz\in
V{\setminus}\\{u,v\\}\mid\exists y\in V(P)\colon d_{G-F}(y,z)\\\
\leqslant\frac{\varepsilon}{9}\cdot\min(\hskip
1.00006pt|P[u..y]|,|P[y..v]|\hskip 1.00006pt)\big{\\}}.$

$P$ is _far away_ 111111Our definition relaxes the one in (Chechik et al.,
2017) in that we allow
$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap\\{s,t\\}\neq\emptyset$ if
$\\{s,t\\}\nsubseteq V(F)$. This makes the definition independent of the
vertices $s$ and $t$ in the query. The proof of Lemma 5.3 remains the same
using $V(F)$ instead of $V(H^{F})$.  from $F$ if it exists in $G-F$ and
$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap V(F)=\emptyset$.

$u=x\in V(F)$$v\in V(F)$$y$$z\in
V(F)$$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)$$P=P(u,v,F)$ Figure 1. A
visualization of the trapezoid $\operatorname{tr}^{\varepsilon/9}_{G-F}(P)$ in
Lemma 5.3 for the case $u=x$. The endpoints $u,v$ are not part of
$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)$. The replacement path from $y$ to
$z$ has length at most $\frac{\varepsilon}{9}\hskip 1.00006ptd_{G-F}(u,y)$.
The smaller trapezoid around $P[u..y]\circ P(y,z,F)$ (red dashed line) does
not contain any vertex from $V(F)$.

The endpoints $u,v$ of $P$ are removed from the trapezoid to exclude
trivialities when applying it to paths between vertices contained in the
failing edges. Finally, note that, due to $\varepsilon/9<1$, the distance from
$u$ to any vertex in the trapezoid is strictly smaller than
$d_{G^{\prime}}(u,v)$ (by symmetry, this also holds for $v$). The idea is that
either the path $P$ is already far away from all failures, or we can reach our
destination via a vertex $z\in\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap
V(F)$ such that the shortest $u$-$z$-path in $G-F$ is far away from $F$ and
only a slight detour. An illustration is given in Figure 1.

###### Lemma 5.3 (Lemma 2.6 in (Chechik et al., 2017)).

Let $u,v\in V(F)$ and $P=P(u,v,F)$ be their replacement path. If
$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap V(F)\neq\emptyset$, then there
are vertices $x\in\\{u,v\\}$, $y\in V(P)$, and
$z\in\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap V(F)$ satisfying

  1. (i)

$|P[x..y]|\leqslant|P|/2$;

  2. (ii)

$d_{G-F}(y,z)\leqslant\frac{\varepsilon}{9}\cdot d_{G-F}(x,y)$;

  3. (iii)

$\operatorname{tr}^{\varepsilon/9}_{G-F}(P[x..y]\circ P(y,z,F))\cap
V(F)=\emptyset$.

In particular, the path $P[x..y]\circ P(y,z,F)$ is far away from all failures
and has length at most $(1+\tfrac{\varepsilon}{9})\cdot d_{G-F}(x,y)$.

We now turn to expaths. Afek et al. (2002) showed that shortest paths in $G-F$
are $f$-_decomposable_ , that is, each of them is obtained by concatenating at
most $f+1$ shortest paths in $G$ (for weighted $G$ those shortest paths may be
interleaved with up to $f$ edges). One would like to represent replacement
paths by the $O(f)$ endpoints of those shortest paths (and edges), but during
the construction of the FT-trees much more than $f$ edges may fail, so this is
not directly possible. We will see that expaths offer a suitable alternative.

###### Definition 5.4 ($\ell$-decomposable path).

Let $A\subseteq E$ be a set of edges and $\ell$ a positive integer. An
$\ell$_-decomposable_ path in $G-A$ is a path which is the concatenation of at
most $\ell+1$ shortest paths of $G$.

###### Definition 5.5 ($\ell$-expath).

Let $A\subseteq E$ be a set of edges and $\ell$ a positive integer. An
$\ell$-_expath_ in $G-A$ is a path that is a concatenation of
$(2\log_{2}(n)+1)$ $\ell$-decomposable paths such that, for every $0\leqslant
i\leqslant 2\log_{2}n$, the length of the $i$-th path is at most
$\min(2^{i},2^{2\log_{2}(n)-i})$.

Since $n\,{-}\,1$ is an upper bound on the diameter of any connected subgraph
of $G$, the middle level $i\,{=}\,\log_{2}n$ is large enough to accompany any
(decomposable) path. Levels may be empty. Therefore, for any
$\ell^{\prime}\geqslant\ell$, an $\ell$-decomposable path is also both
$\ell^{\prime}$-decomposable and an $\ell^{\prime}$-expath. Also, an arbitrary
subpath of an $\ell$-decomposable path (respectively, $\ell$-expath) is again
$\ell$-decomposable (respectively, an $\ell$-expath). This gives the following
intuition why it is good enough to work with expaths. Suppose some replacement
path $P(u,v,F)$ survives in $G{-}A$ albeit $A\supseteq F$ may be much larger
than $F$, then the shortest $u$-$v$-path in $G-A$ is indeed $P(u,v,F)$ and
thus $f$-decomposable. The length of the shortest $(2f{+}1)$-expath between
$u$ and $v$ in $G{-}A$ is the actual replacement distance
$|P(u,v,F)|=d_{G-F}(u,v)$. The reason for the choice $\ell=2f+1$ will become
apparent in the proof of Lemma 5.6. The difficulties of working merely with
$(2f{+}1)$-_decomposable_ paths are described in Lemma 5.11.

Finally, we define a set $B$ of special vertices of $G$ that we call _pivots_.
Recall that we are mainly interested in paths with more than $L$ edges.
Suppose $L=\omega(\log n)$. We construct the set $B$ by sampling any vertex
from $V$ independently with probability $C^{\prime}f\log_{2}(n)/L$ for some
sufficiently large constant $C^{\prime}>0$. With high probability, we have
$|B|=\widetilde{O}(n/L)$ and any replacement path with more than $L/2$ edges
in any of the graphs $G-F$ with $|F|\leqslant f$ contains a pivot as can be
seen by standard Chernoff bounds, see e.g. (Grandoni and Vassilevska Williams,
2020; Roditty and Zwick, 2012; Weimann and Yuster, 2013).

Interface of Data Structure _FT_. For a positive integer $\ell$ and vertices
$u,v\in V$, define $d^{(\ell)}_{\varepsilon/9}(u,v,F)$ to be the minimum
length over all $\ell$-_decomposable_ paths between $u$ and $v$ in $G-F$ that
are far away from $F$. If there are no such paths, we set
$d^{(\ell)}_{\varepsilon/9}(u,v,F)=+\infty$. The data structure _FT_ can only
be queried with triples $(u,v,F)$ for which $u$ or $v$ is a pivot in $B$. Its
returned value satisfies $d_{G-F}(u,v)\leqslant FT(u,v,F)\leqslant 3\cdot
d^{(2f+1)}_{\varepsilon/9}(u,v,F)$. We let $q_{FT}$ denote its query time.

###  5.2. Querying the Distance Sensitivity Oracle

We show how to use the black box _FT_ to get a $(3{+}\varepsilon)$-approximate
$f$-DSO. Fix a query $(s,t,F)$ that we want to answer on the top level. Let
$u,v\in V$ be any two vertices. Recall that we use $d_{G-F}^{\leqslant
L}(u,v)$ for the minimum length over all short $u$-$v$-paths in the graph
$G-F$, and $\widehat{d^{\leqslant L}}(u,v,F)$ for its $(2k{-}1)$-approximation
by the $f$-DSO for short paths described in Theorem 1.2. We instantiate that
oracle with $k=2$. The time to obtain the estimate is
$\widetilde{O}(L^{o(1)})$.

To answer $(s,t,F)$, we build the complete graph $H^{F}$ on the vertex set
$V(H^{F})=\\{s,t\\}\cup V(F)$ and assign weights to its edges. For a pair
$\\{u,v\\}\in\binom{V(H^{F})}{2}$, let $w_{H^{F}}(u,v)$ denote the weight of
the edge $\\{u,v\\}$. Since $G$ is undirected, $w_{H^{F}}(\cdot,\cdot)$ is
symmetric. We allow possibly infinite edge weights instead of removing the
respective edge in order to simplify notation. If $u$ or $v$ is a pivot, we
set $w_{H^{F}}(u,v)$ to the minimum of $\widehat{d^{\leqslant L}}(u,v,F)$ and
$FT(u,v,F)$. Otherwise, if $\\{u,v\\}\cap B=\emptyset$, we set it to the
minimum of $\widehat{d^{\leqslant L}}(u,v,F)$ and
$w_{H^{F}}^{\prime}(u,v)=\min_{b\in B}\left\\{FT(u,b,F)+FT(b,v,F)\right\\}$.
The eventual answer to the query $(s,t,F)$ is the distance $d_{H^{F}}(s,t)$.

###### Lemma 5.6.

W.h.p. the query time is $\widetilde{O}(L^{o(1)}+\frac{n}{L}\cdot q_{FT})$ and
it holds that $d_{G-F}(s,t)\leqslant
d_{H^{F}}(s,t)\leqslant(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(s,t)$.

###### Proof.

The graph $H^{F}$ has $O(f^{2})=O(1)$ edges, and assigning a weight takes
$\widetilde{O}(L^{o(1)}+|B|\cdot q_{FT})$ per edge. The distance from $s$ to
$t$ can be computed using Dijkstra’s algorithm in time $O(f^{2})$.

We prove the seemingly stronger assertion that for each pair $u,v\in
V(H^{F})$, we have $d_{G-F}(u,v)\leqslant
d_{H^{F}}(u,v)\leqslant(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(u,v)$. The
first inequality is immediate from the fact that the values
$\widehat{d^{\leqslant L}}(u,v,F)$, $FT(u,v,F)$, and $FT(u,b,F)+FT(b,v,F)$ for
any $b\in B$ are all at least $d_{G-F}(u,v)$.

We prove the second inequality by induction over $d_{G-F}$. The case $u=v$ is
trivial. Assume the inequality holds for all pairs of vertices with
replacement distance strictly smaller than $d_{G-F}(u,v)$. We distinguish
three cases. In the first case, the (unique) replacement path $P=P(u,v,F)$ has
at most $L$ edges. Theorem 1.2 then implies $d_{H^{F}}(u,v)\leqslant
w_{H^{F}}(u,v)\leqslant\widehat{d^{\leqslant L}}(u,v,F)\leqslant 3\cdot
d_{G-F}^{\leqslant L}(u,v)=3\cdot|P|$, which is $3\hskip
1.00006ptd_{G-F}(u,v)$ as $P$ is a replacement path.

If the path $P$ is long instead, it contains a pivot $b\in B$ w.h.p. (possibly
$u=b$ or $v=b$). For the second case, assume $P$ has more than $L$ edges and
is far away from all failures in $F$. Note that then the subpaths $P[u..b]$
and $P[b..v]$ are the replacement paths for their respective endpoints, and
therefore both $f$-decomposable (and also $(2f{+}1)$-decomposable). Moreover,
they are far away from all failures as their trapezoids are subsets of
$\operatorname{tr}^{\varepsilon/9}_{G-F}(P)$. It holds that

$\displaystyle d_{H^{F}}(u,v)$ $\displaystyle\leqslant w_{H^{F}}(u,v)\leqslant
FT(u,b,F)+FT(b,v,F)$ $\displaystyle\leqslant 3\cdot
d^{(2f+1)}_{\varepsilon/9}(u,b,F)+3\cdot d^{(2f+1)}_{\varepsilon/9}(b,v,F)$
$\displaystyle=3\cdot|P[u..b]|+3\cdot|P[b..v]|=3\cdot d_{G-F}(u,v).$

Finally, for the third case suppose the replacement path $P$ is long but _not_
far away from $F$. Lemma 5.3 states the existence of three vertices
$x\in\\{u,v\\}$, $y\,{\in}\,V(P)$, and
$z\,{\in}\,\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap V(F)$ such that
$d_{G-F}(z,y)\leqslant\tfrac{\varepsilon}{9}\,{\cdot}\,d_{G-F}(x,y)$. The path
$P^{\prime}=P[x..y]\circ P(y,z,F)$ is far away from all failures and has
length at most $(1+\tfrac{\varepsilon}{9})\cdot d_{G-F}(x,y)$. In the
remainder, we assume $x=u$; the argument for $x=v$ is symmetric. If the
concatenation $P^{\prime}$ has at most $L$ edges, we get
$w_{H^{F}}(u,z)\leqslant\widehat{d^{\leqslant L}}(u,z,F)\leqslant 3\hskip
1.00006pt|P^{\prime}|\leqslant 3\left(1+\frac{\varepsilon}{9}\right)\hskip
1.00006ptd_{G-F}(u,y)$.121212We do mean $d_{G-F}(u,y)$ here and _not_
$d_{G-F}(u,z)$.  The latter is equal to
$(3+\frac{\varepsilon}{3})\,d_{G-F}(u,y)$.

Note that $P[u..y]$ is in fact the unique replacement path $P(u,y,F)$. So, if
$P^{\prime}$ has more than $L$ edges, one of its subpaths $P[u..y]$ or
$P(y,z,F)$ has more than $L/2$ edges. Thus, there exists a pivot $b$ on
$P^{\prime}$. Here, we actually use the uniqueness of shortest paths in $G$
since replacing, say, $P[u..y]$ with another shortest $u$-$y$-path in $G-F$ to
ensure a pivot may result in a concatenation that is no longer far away from
all failures. Similar to the second case, we arrive at

$\displaystyle w_{H^{F}}(u,z)$ $\displaystyle\leqslant FT(u,b,F)+FT(b,z,F)$
$\displaystyle\leqslant 3\cdot d^{(2f+1)}_{\varepsilon/9}(u,b,F)+3\cdot
d^{(2f+1)}_{\varepsilon/9}(b,z,F)$ $\displaystyle\leqslant
3\cdot|P^{\prime}[u..b]|+3\cdot|P^{\prime}[b..z]|\leqslant\left(3+\frac{\varepsilon}{3}\right)d_{G-F}(u,y).$

It is important that _FT_ approximates $d^{(2f+1)}_{\varepsilon/9}$ because
$P^{\prime}$ may not be $f$-decomposable, but it is the concatenation of two
$f$-decomposable paths and thus $(2f{+}1)$-decomposable; so are
$P^{\prime}[u..b]$ and $P^{\prime}[b..z]$.

Now that we have an upper bound on $w_{H^{F}}(u,z)$ we can conclude the third
case. Since $\tfrac{\varepsilon}{9}<1$ and
$z\in\operatorname{tr}^{\varepsilon/9}_{G_{F}}(P)$ (where $P$ is the
$u$-$v$-replacement path), the distance $d_{G-F}(z,v)$ is strictly smaller
than $d_{G-F}(u,v)$. By induction,
$d_{H^{F}}(z,v)\leqslant(3{+}\varepsilon)\cdot d_{G-F}(z,v)$. Recall that
vertex $y$ lies on $P$, whence $d_{G-F}(u,y)+d_{G-F}(y,v)=d_{G-F}(u,v)$. Due
to $\varepsilon\leqslant 3$, we have
$(2{+}\tfrac{\varepsilon}{3})\tfrac{\varepsilon}{9}\leqslant\tfrac{\varepsilon}{3}$.
Also, recall that $d_{G-F}(z,y)\leqslant\tfrac{\varepsilon}{9}\hskip
1.00006ptd_{G-F}(u,y)$ by the definition of $z$ and $x=u$. Putting everything
together, we estimate the $u$-$v$-distance in the graph $H^{F}$.

$\displaystyle d_{H^{F}}(u,v)\leqslant w_{H^{F}}(u,z)+d_{H^{F}}(z,v)$
$\displaystyle\leqslant\left(3+\frac{\varepsilon}{3}\right)d_{G-F}(u,y)+(3+\varepsilon)d_{G-F}(z,v)$
$\displaystyle=3\left(\left(1+\frac{\varepsilon}{9}\right)d_{G-F}(u,y)+\left(1+\frac{\varepsilon}{3}\right)\left(d_{G-F}(z,y)+d_{G-F}(y,v)\right)\right)$
$\displaystyle\leqslant
3\left(\left(1+\frac{\varepsilon}{9}\right)d_{G-F}(u,y)+\left(1+\frac{\varepsilon}{3}\right)\left(\frac{\varepsilon}{9}d_{G-F}(u,y)+d_{G-F}(y,v)\right)\right)$
$\displaystyle=3\Big{(}d_{G-F}(u,y)+d_{G-F}(y,v)+\left(2+\frac{\varepsilon}{3}\right)\\!\frac{\varepsilon}{9}d_{G-F}(u,y)+\frac{\varepsilon}{3}d_{G-F}(y,v)\\!\Big{)}$
$\displaystyle\leqslant
3\Big{(}d_{G-F}(u,v)+\frac{\varepsilon}{3}d_{G-F}(u,y)+\frac{\varepsilon}{3}d_{G-F}(y,v)\Big{)}=(3{+}\varepsilon)d_{G-F}(u,v).\qed$

###  5.3. Fault-Tolerant Trees

We now describe the implementation of the _FT_ data structure via fault-
tolerant trees. We compute all-pairs shortest distances in the original graph
$G$ (if required, with perturbed edge weights for unique shortest paths), and,
for each pivot $b\in B$, a shortest path tree of $G$ rooted in $b$ in
$\widetilde{O}(mn)$ time. We turn each of those trees into a data structure
that reports the lowest common ancestor (LCA) in constant time with the
algorithm of Bender and Farach-Colton (2000). This takes time and space
$O(|B|n)=\widetilde{O}(n^{2}/L)$ w.h.p.

We also assume that we have access to a procedure that, given any set
$A\subseteq E$ of edges (which may have much more than $f$ elements) and pair
of vertices $u,v\in V$, computes the shortest $(2f{+}1)$-expath between $u$
and $v$ in $G{-}A$. This expath is labeled with its structure, that means, (a)
the start and endpoints of the $2\log_{2}(n)+1$ constituting
$(2f{+}1)$-decomposable subpaths, and (b) inside each decomposable path the
start and endpoint of the constituting shortest paths (and possibly
interleaving edges). We explain in Appendix B how to achieve this in time
$\widetilde{O}(fm)$, this is also the key ingredient of the proof of Theorem
1.4.

We build the FT-trees only for pairs of vertices $(u,b)$ for which $b\in B$ is
a pivot. On a high level, $FT(u,b)$ is a tree of depth $f$ that stores in each
node the shortest $(2f{+}1)$-expath between $u$ and $b$ in some graph $G{-}A$.
We first describe the information that we hold in a single node $\nu$. Let
$P_{\nu}$ be the stored expath. It is partitioned first into segments and
those into parts. To define the segments, we need the notion of netpoints.

###### Definition 5.7 (Path netpoints).

Let $P=(u=v_{1},\dots,v_{\ell}=b)$ be a path. Define $p_{\text{left}}$ to be
all vertices $v_{j},v_{j+1}\in V(P)$ such that
$|P[u..v_{j}]|<(1+\tfrac{\varepsilon}{36})^{i}\leqslant|P[u..v_{j+1}]|$ for
some integer $i\geqslant 0$. Analogously, let $p_{\text{right}}$ be all
vertices $v_{j},v_{j-1}\in V(P)$ such that
$|P[v_{j}..b]|<(1+\tfrac{\varepsilon}{36})^{i}\leqslant|P[v_{j-1}..b]|$ for
some $i$. The _netpoints_ of $P$ are all vertices in $p_{\text{left}}\cup
p_{\text{right}}\cup\\{u,b\\}$.

A _segment_ of the path $P$ is the subpath between consecutive netpoints. For
an edge $e\in E(P)$, let $\operatorname{seg}(e,P)$ denote the segment of $P$
containing $e$. The netpoints cut $P$ into segments of exponentially
increasing length, with $1+\tfrac{\varepsilon}{36}$ being the base of the
exponential. However, since we do this from _both_ ends the segments do not
get too large. We make this precise in Lemma 5.10 below.

The segments are further subdivided into parts. An expath $P$ consists of
decomposable subpaths, which in turn consist of shortest paths (and
interleaving edges) in $G$, but they may not be aligned with the segments. To
avoid this, we define a _part_ of $P$ to be a maximal subpath that is
completely contained in a shortest path of a $(2f{+}1)$-decomposable subpath
and also does not cross netpoints. We can find all parts by a linear scan over
the labels of the expath given by the procedure mentioned above. Note that
each part is a shortest path/edge in $G$. By the assumption that shortest
paths are unique, it is enough to represent a part by its two endpoints. With
each part $[v,w]$, for $v,w\in V(P)$, we keep the information whether one or
both endpoints are netpoints, store the original graph distance $d(v,w)$, and
a marker whether that part is long, i.e., whether it contains more than $L$
edges. If so, we additionally store a pivot $p\in B$ that lies in that part.
(The case $p=b$ is possible if the respective part lies at the end of the
expath $P$, that is, if $w=b$.)

We now describe the whole FT-tree $FT(u,b)$ recursively. In some node $\nu$,
let $A_{\nu}$ be the set of all edges that were failed in the path from the
root to $\nu$; with $A_{\nu}=\emptyset$ in the root itself. We compute the
shortest $(2f{+}1)$-expath $P_{\nu}$ in $G-A_{\nu}$ and store the information
for all its parts. For each of its segments $S$, we create a child node $\mu$
in which we set $A_{\mu}=A_{\nu}\cup E(S)$. That means, the transition from a
parent to a child corresponds to failing the _whole segment_. Note that the
sets $A_{\nu}$ are only used during preprocessing and never actually stored.
We continue the recursive construction until depth $f$ is reached; if in a
node $\nu$ the vertices $u$ and $b$ become disconnected, we mark this as a
leaf node not storing any path. We build one FT-tree for each pair of
(distinct) vertices in $V\times B$ and additionally store the LCA data
structure for each pivot.

The number of segments of any simple path in a subgraph of $G$ is at most
$2\log_{1+\tfrac{\varepsilon}{36}}(n)+1$. Therefore, there exists a constant
$c>0$ such that the maximum number of segments of one path is at most $c\hskip
1.00006pt\log_{2}(n)/\varepsilon$. This is an upper bound on the degree of any
node, so there are at most $(c\hskip 1.00006pt\log_{2}(n)/\varepsilon)^{f}$
nodes in each tree. Moreover, an $(2f{+}1)$-expath consists of $O(f\log n)$
shortest paths. So there are $O(f\log^{2}n/\varepsilon)$ parts in one node,
for each of which we store a constant number of machine words. In summary, all
FT-trees and LCA structures together take space

$|B|n\cdot O\\!\left(\frac{f\log^{2}n}{\varepsilon}\right)\cdot
O\\!\left(\frac{\log
n}{\varepsilon}\right)^{f}+O(|B|n)=\widetilde{O}\\!\left(\frac{n^{2}}{L}\right)\cdot
O\\!\left(\frac{\log n}{\varepsilon}\right)^{f+1}.$

The time spent in each node is dominated by computing the $(2f{+}1)$-expath.
The total time to precompute _FT_ is
$|B|n\cdot\widetilde{O}\\!\left(fm+\frac{1}{\varepsilon}\right)\cdot
O\\!\left(\frac{\log
n}{\varepsilon}\right)^{f}+O(|B|n)=\widetilde{O}\\!\left(\frac{n^{2}}{L}\left(m+\frac{1}{\varepsilon}\right)\right)\cdot
O\\!\left(\frac{\log n}{\varepsilon}\right)^{f}$.

###  5.4. Querying the Data Structure _FT_

We used in Lemma 5.6 that the returned value $FT(u,b,F)$ is at least
$d_{G-F}(u,b)$ and most $3\,d^{(2f+1)}_{\varepsilon/9}(u,b,F)$, three times
the minimum length of an $(2f{+}1)$-decomposable between $u$ and $b$ in
$G{-}F$ that is far away from all failures in $F$. We now show how to do this.

The main challenge when traversing the FT-tree is to utilize the little
information that is stored in a node $\nu$ to solve the following problem.
Either find the segment $\operatorname{seg}(e,P_{\nu})$ for some failing edge
$e\in F$ or verify that $F\cap E(P_{\nu})=\emptyset$. The original solution in
(Chechik et al., 2017) was to compare for each shortest path/interleaving edge
$[v,w]$ on $P_{\nu}$ and edge $e=\\{x,y\\}\in F$ whether the minimum of
$d(v,x)+w(x,y)+d(y,w)$ and $d(v,y)+w(x,y)+d(x,w)$ is equal to $d(v,w)$. If so,
$e$ must lie on the shortest path $P_{\nu}[v..w]$. Finding the according
segment amounts to computing the two bounding netpoints with a binary search.
The problem is that this approach requires to store all $\Omega(n^{2})$
original graph distances in $G$, which we cannot afford. We first prove that
we can get a weaker guarantee with our setup.

###### Lemma 5.8.

Let $\nu$ be a node of $FT(u,b)$. There exists an algorithm to check that
there is a path between $u$ and $b$ in $G-F$ that has length at most $3\hskip
1.00006pt|P_{\nu}|$ or find the segment $\operatorname{seg}(e,P_{\nu})$ for
some $e\in F\cap E(P_{\nu})$. The computation time is
$\widetilde{O}(L^{o(1)}/{\varepsilon})$.

###### Proof.

Note that one of the alternatives must occur for if $F\cap
E(P_{\nu})=\emptyset$, then $P_{\nu}$ exists in $G-F$. Consider a part $[v,w]$
of $P_{\nu}$. If it has more than $L$ edges, then we stored a pivot $p$ in
$[v,w]$. More precisely, $[v,w]$ is the concatenation of the unique shortest
path between $v$ and $p$ and the one between $p$ and $w$ in $G$. We have
access to a shortest path tree rooted in $p$. So, for each edge
$e=\\{x,y\\}\in F$, we can check with a constant number of LCA queries
involving $p$, $v$, $w$, $x$, and $y$ whether edge $e$ is in that
concatenation in time $O(f)$ per part. If all checks fail, we have
$d_{G-F}(v,w)=d(v,w)=|P_{\nu}[v..w]|$.

If $[v,w]$ is short, the oracle from Theorem 1.2 is queried with the triple
$(v,w,F)$. That oracle was preprocessed anyway and answers in time
$\widetilde{O}(L^{o(1)})$. The return value $\widehat{d^{\leqslant L}}(v,w,F)$
is compared with the original distance $d(v,w)$ that was stored with the part.
If the former is more than $3$ times the latter, it must be that
$d_{G-F}(v,w)>d(v,w)$, so the part contains some edge of $F$.

We either find a part that has a failing edge in total time
$\widetilde{O}(L^{o(1)}\cdot f\hskip
1.00006pt\frac{\log^{2}n}{\varepsilon})=\widetilde{O}(L^{o(1)}/{\varepsilon})$
or verify that $d_{G-F}(v,w)\leqslant 3\cdot d(v,w)$ holds for _all_ parts. In
the latter case, swapping each part $[v,w]$ by its replacement path $P(v,w,F)$
shows the existence of a path in $G-F$ of length at most
$3|P_{\nu}|=\sum_{[v,w]}3\hskip 1.00006ptd(v,w)$. Finally, let $[v,w]$ be a
part with $E([v,w])\cap F\neq\emptyset$. It is completely contained in a
segment, finding the two closest netpoints on the subpaths $P_{\nu}[u..v]$ and
$P_{\nu}[w..b]$ takes only $O(\log
n/\varepsilon)=\widetilde{O}(1/\varepsilon)$ additional time. ∎

We use the lemma to compute $FT(u,b,F)$. The tree transversal starts at the
root. Once it enters a node $\nu$, it checks whether there is a path in $G-F$
of length at most $3\hskip 1.00006pt|P_{\nu}|$. If so, this length is
returned. Otherwise, the algorithm obtains a segment
$\operatorname{seg}(e,P_{\nu})$ for some $e\in F\cap E(P_{\nu})$ and recurses
on the corresponding child. Once a leaf $\nu^{*}$ is encountered, the length
$|P_{\nu^{*}}|$ is returned; or $+\infty$ if the leaf does not store a path.
This takes total time $q_{FT}=\widetilde{O}(L^{o(1)}/\varepsilon)$ since at
most $f{+}1=O(1)$ nodes are visited. The main argument for the correctness of
this procedure is to show that if a $(2f{+}1)$-expath $P$ in $G-F$ is far away
from all failures, it survives in $G-A_{\nu^{*}}$.

###### Lemma 5.9.

Let $P$ be the shortest $(2f{+}1)$-decomposable path between $u$ and $b$ in
$G-F$ that is far away from all failures in $F$. Let $\nu^{*}$ be the node of
$FT(u,b)$ in which a value is returned when queried with $F$, and let
$A_{\nu^{*}}$ be the set of edges that were failed from the root to $\nu^{*}$.
Then, $P$ exists in the graph $G-A_{\nu^{*}}$. Moreover, it holds that
$d_{G-F}(u,b)\leqslant FT(u,b,F)\leqslant 3\cdot
d^{(2f+1)}_{\varepsilon/9}(u,b,F)$.

We need the following two lemmas for the proof. The first one states that the
segments of a path are not too long, or even only contain a single edge. The
second lemma verifies a certain prefix optimality of expaths. This is the
crucial property that decomposable paths are lacking. For some edge set
$A\subseteq E$, let $d^{(\ell)}(u,v,A)$ be the length of the shortest
$\ell$-_decomposable_ path in $G{-}A$. Compared to
$d^{(\ell)}_{\varepsilon/9}(u,v,F)$, this definition allows for larger failure
sets and drops the requirement of the path being far away from the failures.

###### Lemma 5.10 (Lemma 3.2 in (Chechik et al., 2017)).

Let $u\in V$ and $b\in B$, $P$ be any path between $u$ and $b$, $e\in E(P)$,
and $y$ a vertex of the edge $e$. Then, $E(\operatorname{seg}(e,P))=\\{e\\}$
or
$|\operatorname{seg}(e,P)|\leqslant\tfrac{\varepsilon}{36}\min(|P[u..y]|,|P[y..b]|)$.

###### Lemma 5.11 (Lemma 3.1 in (Chechik et al., 2017)).

Let $u\in V$ and $b\in B$, $A\subseteq E$ a set of edges, $\ell$ a positive
integer, and $P$ the shortest $\ell$-expath between $u$ and $b$ in $G-A$.
Then, for every $y\in V(P)$, $|P[u..y]|\leqslant 4\cdot d^{(\ell)}(u,y,A)$ and
$|P[y..v]|\leqslant 4\cdot d^{(\ell)}(y,v,A)$ both hold.

###### Proof of Lemma 5.9.

The second assertion is an easy consequence of the first. $P$ is the shortest
$(2f{+}1)$-decomposable $u$-$b$-path in $G-F$ that is far away from all
failures in $F$. If $P$ also exists in $G-A_{\nu^{*}}$, then
$|P_{\nu^{*}}|\leqslant|P|$ by the definition of $P_{\nu^{*}}$ as the shortest
$(2f{+}1)$-expath between $u$ and $v$ in $G-A_{\nu^{*}}$ and $P$ being
$(2f{+}1)$-decomposable (and thus a $(2f{+}1)$-expath). The query algorithm
guarantees $FT(u,b,F)\leqslant 3\hskip 1.00006pt|P_{\nu^{*}}|\leqslant 3\hskip
1.00006pt|P|=3\cdot d^{(2f+1)}_{\varepsilon/9}(u,b,F)$. It is clear that we
never underestimate the true distance $d_{G-F}(u,b)$.

We show the existence of the path $P$ in $G-A_{\nu}$ for _every_ visited node
$\nu$ by induction over the parent-child transitions of the tree transversal.
It is true for the root where $A_{\nu}=\emptyset$. When going from $\nu$ to a
child, $A_{\nu}$ gets increased by the edges
$E(\operatorname{seg}(e,P_{\nu}))$ of a segment for some $e_{F}\in F\cap
E(P_{\nu})$. It is enough to prove that $P$ does not contain an edge of
$\operatorname{seg}(e,P_{\nu})$. Intuitively, we argue that the segments are
too short for their removal to influence a path far away from $F$.

The claim is immediate if $E(\operatorname{seg}(e_{F},P_{\nu}))=\\{e_{F}\\}$,
because $P$ exists in $G-F$. For the remainder, suppose
$\operatorname{seg}(e_{F},P_{\nu})$ consists of more than one edge. To reach a
contradiction, assume $e_{P}\in E(P)\cap E(\operatorname{seg}(e_{F},P_{\nu}))$
is an edge in the intersection. If $\operatorname{seg}(e_{F},P_{\nu})$
contains multiple edges from $F$, we let $e_{F}$ be the one closest to
$e_{P}$. This ensures that the subpath of $P_{\nu}$ between the closest
vertices in $e_{F}$ and $e_{P}$ does not contain any other failing edges. More
formally, there are vertices $y\in e_{P}$ and $z\in e_{F}$ such that neither
$y$ nor $z$ are the endpoints $u$ or $b$ and the subpath $P_{\nu}[y..z]$ lies
entirely both in $\operatorname{seg}(e,P_{\nu})$ and the graph $G-F$. Since
$y\in V(P)$, $z\in V(F)$, and the path $P$ is far away from all failures, $z$
must be outside of the trapezoid $\operatorname{tr}^{\varepsilon/9}_{G-F}(P)$,
that is, $|\operatorname{seg}(e_{F},P_{\nu})|\geqslant|P_{\nu}[y..z]|\geqslant
d_{G-F}(y,z)>\frac{\varepsilon}{9}\min(|P[u..y]|,|P[y..b]|)$. Conversely, we
combine Lemmas 5.10 and 5.11, the fact that edge $e_{P}$ lies both on $P$ and
$P_{\nu}$, as well as $P_{\nu}$ (with its subpaths) being a $(2f{+}1)$-expath
to arrive at

$\displaystyle|\operatorname{seg}(e_{F},P_{\nu})|$
$\displaystyle\leqslant\frac{\varepsilon}{36}\min(|P_{\nu}[u..y]|,|P_{\nu}[y..b]|)$
$\displaystyle\leqslant\frac{\varepsilon}{36}\cdot\min\\!\left(4\cdot
d^{(2f+1)}(u,y,F),\ 4\cdot d^{(2f+1)}(y,b,F)\right)$
$\displaystyle\leqslant\frac{\varepsilon}{9}\cdot\min(|P[u..y]|,|P[y..b]|).\qed$

###  5.5. Proof of Lemma 5.1

We derive the parameters of the $f$-DSO with sublinear query time. The
preprocessing consists of two main parts. First, the oracle for short paths is
computable in time $\widetilde{O}(L^{f+o(1)}\hskip 1.00006ptm\sqrt{n})$
(Theorem 1.2). Secondly, $FT$ has preprocessing time
$\widetilde{O}((n^{2}/L)(m+1/\varepsilon))O(\log n/\varepsilon)^{f}$, assuming
that we can compute expaths in time $\widetilde{O}(fm)$. We set
$L=n^{\alpha/(f+1)}$ for a constant $0<\alpha<1/2$. The total preprocessing
time is dominated by the FT-trees giving a total time of
$O(n^{2-\frac{\alpha}{f+1}}(m+1/\varepsilon))\cdot O(\log n/\varepsilon)^{f}$.
By Lemma 5.6 with $q_{FT}=\widetilde{O}(L^{o(1)}/\varepsilon)$ the query time
of the resulting oracle is $\widetilde{O}(n/\varepsilon
L^{1-o(1)})=n^{1-\frac{\alpha}{f+1}+o(1)}/\varepsilon$. The data structure
from Theorem 1.2 requires space $\widetilde{O}(L^{f+o(1)}n^{3/2})$, and _FT_
takes $\widetilde{O}(n^{2}/L)\cdot O(\log n/\varepsilon)^{f+1}$. Inserting our
choice of $L$ gives
$n^{\frac{f}{f+1}\alpha+\frac{3}{2}+o(1)}+\widetilde{O}\\!\left(n^{2-\frac{\alpha}{f+1}}\right)\cdot
O\\!\left(\frac{\log n}{\varepsilon}\right)^{f+1}$. Since $\alpha<1/2$ is a
constant, the second term dominates.

##  6\. Reducing the Query Time

We now reduce the query time to $O_{\varepsilon}(n^{\alpha})$. The bottleneck
of the query answering is computing the (auxiliary) weight
$w^{\prime}_{H^{F}}(u,v)$ of the edge $\\{u,v\\}$ in the graph $H^{F}$, see
the beginning of Section 5.2. Minimizing $FT(u,b,F)+FT(b,v,F)$ over all pivots
$b$ takes linear time in $|B|$. Let $\lambda=\lambda(L,\varepsilon)\leqslant
L$ be a parameter to be fixed later. We define $\mbox{\rm
ball}_{G-F}(x,\lambda)=\\{z\in V\mid d_{G-F}(x,u)\leqslant\lambda\\}$. If we
had access to the graph $G-F$ at query time, we could run Dijkstra’s algorithm
from $u$ and from $v$ to scan the balls $\mbox{\rm ball}_{G-F}(u,\lambda)$ and
$\mbox{\rm ball}_{G-F}(v,\lambda)$ of radius $\lambda$, and only consider the
pivots that are inside these balls. By carefully adapting the sampling
probability of the pivots to $\widetilde{O}(n/\lambda)$, we ensure at least
one of them hits the shortest expath (replacement path) for from $u$ to $v$
w.h.p. (more details below). The problem is that these balls may still contain
too many pivots. In the worst case, we have, say, $\mbox{\rm
ball}_{G-F}(u,\lambda)\cap B=B$ degenerating again to the need to scan _all_
pivots. Furthermore, we cannot even afford to store all balls as there are
$\Omega(nm^{f})$ different ones, a ball for each pair $(x,F)$. Finally, the
assumption of access to $G-F$ itself is problematic in the subquadratic-space
regime.

To handle all these issues, we consider two cases when computing
$w^{\prime}_{H^{F}}(u,v)$. That of _sparse balls_ , where at least one of
$\mbox{\rm ball}_{G-F}(u,\lambda)$ and $\mbox{\rm ball}_{G-F}(v,\lambda)$
contains less than $L^{f}$ vertices, and the case of _dense balls_ where the
two sets both contain more than $L^{f}$ vertices.

###  6.1. The Case of Sparse Balls

Consider the same setup as in Section 5.1, only that the pivots for $B$ are
now sampled with probability $C^{\prime\prime}f\log_{2}(n)/\lambda$ for some
$C^{\prime\prime}>0$. By making the constant $C^{\prime\prime}$ slightly
larger than $C^{\prime}$ in the original sampling probability (see the end of
Section 5.1), we ensure that w.h.p. every path that is a _concatenation_ of at
most two replacement paths and has more than $\lambda$ edges contains a pivot.
(Previously, we only had this for ordinary replacement paths with at least
$L/2$ edges.) Note that all statements from Section 5 except for the space,
preprocessing and query time in Lemma 5.1 remain true. Further, observe that
in the case of sparse balls, w.h.p. there are $\widetilde{O}(L^{f}/\lambda)$
pivots in $\mbox{\rm ball}_{G-F}(u,\lambda)$ or in $\mbox{\rm
ball}_{G-F}(v,\lambda)$. In this case, it is sufficient to scan those in the
same way as we did above. The only issue is that we do not have access to
$\mbox{\rm ball}_{G-F}(u,\lambda)$ at query time, so we precompute a proxy.

Let $G_{1},\ldots,G_{\kappa}$ be all the subgraphs of $G$ in the leaves of the
sampling trees introduced in Section 4.2. Recall that they form an
$(L,f)$-replacement path covering w.h.p. During preprocessing, we compute and
store the sets $B_{G_{i}}(x,\lambda)=B\cap\mbox{\rm ball}_{G_{i}}(x,\lambda)$
for all the sparse balls $\mbox{\rm ball}_{G_{i}}(x,\lambda)$, that is, if
$|\mbox{\rm ball}_{G_{i}}(x,\lambda)|\leqslant L^{f}$. Otherwise, we store a
marker that $\mbox{\rm ball}_{G_{i}}(x,\lambda)$ is dense.131313 This marker
is made more precise in Section 6.2.  As $\kappa=L^{f+o(1)}$ and w.h.p.
$|B_{G_{i}}(x,\lambda)|=\widetilde{O}(L^{f}/\lambda)$ for sparse balls,
storing all of these sets requires $\widetilde{O}(nL^{2f+o(1)}/\lambda)$
space. One can compute $B_{G_{i}}(x,\lambda)$ by running Dijkstra from $x$ in
$G_{i}$ until at most $L^{f}$ vertices are discovered in time
$\widetilde{O}(L^{2f})$. In total, this takes $\widetilde{O}(nL^{3f+o(1)})$
time.

Suppose we want to compute the weight $w_{H^{F}}(u,v)$ in the sparse balls
case, meaning that there is an $x\in\\{u,v\\}$ such that the true set
$\mbox{\rm ball}_{G-F}(x,\lambda)$ is sparse.141414If this holds for both $u$
and $v$ the choice of $x$ is arbitrary.  We use $y$ to denote the remaining
vertex in $\\{u,v\\}{\setminus}\\{x\\}$. Let $i_{1},\ldots,i_{r}$ be the
indices of the graphs $G_{i_{j}}$ that exclude $F$ as computed by Algorithm 3.
We showed in Section 4.2 that $r=\widetilde{O}(L^{o(1)})$ and that the indices
can be found in time proportional to their number. By definition of $x$, all
the proxies $\mbox{\rm ball}_{G_{i_{j}}}(x,\lambda)$ for $1\leqslant
j\leqslant r$ are sparse as well. Departing from Section 5.2, we set

(1) $w^{\prime}_{H^{F}}(u,v)=\min_{\begin{subarray}{c}1\leqslant j\leqslant
r\\\ b\in B_{G_{i_{j}}}(x,\lambda)\end{subarray}}\left(\widehat{d^{\leqslant
L}}(x,b,F)+FT(b,y,F)\right).$

The (actual) weight is
$w_{H^{F}}(u,v)=\min(w^{\prime}_{H^{F}}(u,v),\widehat{d^{\leqslant
L}}(u,v,F))$. Its computation takes time
$\widetilde{O}(L^{f+o(1)}/\varepsilon\lambda)$ as there are
$\widetilde{O}(L^{o(1)})$ balls, each with $\widetilde{O}(L^{f}/\lambda)$
pivots, the values $\widehat{d^{\leqslant L}}$ can be evaluated in time
$L^{o(1)}$ (Theorem 1.2), and we navigate through
$\widetilde{O}(L^{f}/\lambda)$ FT-trees with a query time of
$q_{FT}=\widetilde{O}(L^{o(1)}/\varepsilon)$ each.

Recall the proof of the $(3{+}\varepsilon)$-approximation from Lemma 5.6.
Clearly, if the replacement path $P(u,v,F)$ is short, then
$d_{H^{F}}(u,v)\leqslant 3\cdot d_{G-F}(u,v)$ still holds since the argument
is independent of the definition of $w^{\prime}_{H^{F}}(u,v)$. We make the
next step in recovering what was dubbed the “second case” for sparse balls.
(The proof needs the transition from $\widetilde{O}(n/L)$ to
$\widetilde{O}(n/\lambda)$ pivots.)

###### Lemma 6.1.

Let $u,v\in V$ be such that $|\mbox{\rm ball}_{G-F}(u,\lambda)|\leqslant
L^{f}$ or $|\mbox{\rm ball}_{G-F}(v,\lambda)|\leqslant L^{f}$, and the
replacement path $P(u,v,F)$ is long and far away from all failures in $F$.
Then, with high probability $w_{H^{F}}(u,v)\leqslant 3\cdot d_{G-F}(u,v)$
holds.

###  6.2. The Case of Dense Balls

To transfer the proof of Lemma 5.6, $w_{H^{F}}(u,v)\leqslant 3\,d_{G-F}(u,v)$
would have to be true also if both $\mbox{\rm ball}_{G-F}(u,\lambda)$ and
$\mbox{\rm ball}_{G-F}(v,\lambda)$ are dense and $P(u,v,F)$ is far away from
all failures. If that were our only concern, Equation 1, would ensure that.
However, the query time is $\Omega(n/\lambda)$ since a dense ball may contain
too many pivots. We provide a more efficient query algorithm which, however,
only gives a $(3+\delta)$-approximation for a small $\delta>0$ (Lemma 6.6).
Therefore, we have to adapt the proof of Lemma 5.6.

Our changes to the construction are twofold. We define a set $\mathcal{B}$ of
_new_ pivots, polynomially sparser than $B$, by sampling each vertex
independently with probability $C^{\prime}f\log_{2}n/\lambda L^{f-1}$. By a
Chernoff bound and $\lambda L^{f-1}\leqslant L^{f}$, it holds that w.h.p.
$|\mathcal{B}|=\widetilde{O}(n/\lambda L^{f-1})$ and all sets $\mbox{\rm
ball}_{G-F}(x,\lambda)$ with $|\mbox{\rm ball}_{G-F}(x,\lambda)|>L^{f}$
contain a new pivot. We build an FT-tree with granularity $\lambda$ for each
pair in $\mathcal{B}^{2}$.

FT-Trees with Granularity. Given two new pivots $b_{u},b_{v}\in\mathcal{B}$,
we denote by $FT_{\lambda}(b_{u},b_{v})$ the _fault-tolerant tree of $b_{u}$
and $b_{v}$ with granularity $\lambda$_. Granularity affects the netpoints,
segments and expaths.

###### Definition 6.2 (Path netpoints with granularity $\lambda$).

Let $P=(b_{u}=v_{1},v_{2},\ldots,v_{\ell}=b_{v})$ be a path. If $|P|\leqslant
2\lambda$, then the _netpoints of $P$ with granularity $\lambda$_ are all
vertices $V(P)$ of the path. Otherwise, define $p_{\text{left}}$ to be all
vertices $v_{j},v_{j+1}\in V(P)$ with $\lambda\leqslant
j\leqslant\ell-\lambda$ such that
$|P[v_{\lambda}..v_{j}]|<(1{+}\frac{\varepsilon}{36})^{i}\leqslant|P[v_{\lambda}..v_{j+1}]|$
for some integer $i\geqslant 0$. Analogously, let $p_{\text{right}}$ be all
vertices $v_{j},v_{j-1}\in V(P)$ such that
$|P[v_{j}..v_{\ell-\lambda}]|<(1{+}\frac{\varepsilon}{36})^{i}\leqslant|P[v_{j-1}..v_{\ell-\lambda}]|$
for some $i$. The _netpoints of P with granularity $\lambda$_ are all vertices
in $\\{v_{0},\ldots,v_{\lambda}\\}\cup p_{\text{left}}\cup
p_{\text{right}}\cup\\{v_{\ell-\lambda},\ldots,v_{\ell}\\}$.

For $\lambda=0$, this is the same as Definition 5.7. Similar as before, we
denote by $\operatorname{seg}_{\lambda}(e,P)$ for $e\in P$ the set of
_segment_ w.r.t. to the new netpoints that contains $e$. Any path has
$O(\lambda)+O(\log_{1+\varepsilon}n)=O(\lambda)+O(\log n/\varepsilon)$
netpoints with granularity $\lambda$ and thus so many segments. The number of
nodes per tree is now $(O(\lambda)+O(\log
n/\varepsilon))^{f}=O(\lambda^{f})+O(\log n/\varepsilon)^{f}$ In summary, the
crucial change is that the first and last $\lambda$ edges are in their own
segment and the segment lengths increase exponentially only in the middle
part.

###### Definition 6.3 ($\ell$-expath with granularity $\lambda$).

Let $A\subseteq E$ be a set of edges and $\ell$ a positive integer. An
$\ell$-_expath with granularity_ $\lambda$ in $G-A$ is a path $P_{a}\circ
P_{b}\circ P_{c}$ such that $P_{a}$ and $P_{c}$ contain at most $\lambda$
edges each, while $P_{b}$ is a concatenation of $(2\log_{2}(n){+}1)$
$\ell$-decomposable paths such that, for every $0\leqslant i\leqslant
2\log_{2}n$, the length of the $i$-th $\ell$-decomposable path is at most
$\min(2^{i},2^{2\log_{2}(n)-i})$.

The _parts_ of an $\ell$-expath with granularity $\lambda$ are defined as
before. In each node $\nu$ of $FT_{\lambda}(b_{u},b_{v})$, we store the
shortest $(2f{+}1)$-expath $P_{\nu}$ with granularity $\lambda$ from $b_{u}$
to $b_{v}$ in $G_{\nu}$. Note that $P_{\nu}$ now has
$O(f\log(n)\cdot(\lambda+\log(n)/\varepsilon))$ many parts.

Space and Preprocessing Time. Recall the analysis at the end of Section 5.3,
and also that (compared to that) we changed the size of $|B|$ to
$\widetilde{O}(n/\lambda)$ in Section 6.1. The number of nodes in
$FT_{\lambda}(b_{u},b_{v})$ is $O(\lambda^{f})+O(\log n/\varepsilon)^{f}$ and
we only need $|\mathcal{B}|^{2}=\widetilde{O}(n^{2}/\lambda^{2}L^{2f-2})$ new
trees. With $\lambda\leqslant L$, this makes for
$\widetilde{O}\\!\left(\frac{n^{2}}{L^{f}}\right)+\widetilde{O}\\!\left(\frac{n^{2}}{\lambda^{2}L^{2f-2}}\right)O\\!\left(\frac{\log
n}{\varepsilon}\right)^{f}$ nodes in all new trees. This is less than the
$\widetilde{O}(n^{2}/\lambda)\cdot O(\log n/\varepsilon)^{f}$ we had for the
original FT-trees (that we still need to preprocess). The more efficient
expath computation transfers to expaths with granularity, see Section B.3. We
can compute such a path in asymptotically the same time
$\widetilde{O}(fm)=\widetilde{O}(m)$. So the preprocessing time of the new
trees is dominated by the one for the old trees. Also, the additional
$\widetilde{O}(nL^{3f+o(1)})$ term for the sparse/dense balls will turn out to
be negligible. More importantly, for the total size of the new trees the
number of nodes gets multiplied by $O(\lambda+f\log^{2}(n)/\varepsilon)$,
proportional to the number of parts. The result turns out to be

$\widetilde{O}\\!\left(\frac{n^{2}}{L^{f-1}}\right)+\widetilde{O}\\!\left(\frac{n^{2}}{\lambda
L^{2f-2}}\right)\cdot O\\!\left(\frac{\log n}{\varepsilon}\right)^{f}+\\\
\widetilde{O}\\!\left(\frac{n^{2}}{\varepsilon
L^{f}}\right)+\widetilde{O}\\!\left(\frac{n^{2}}{\lambda^{2}L^{2f-2}}\right)\cdot
O\\!\left(\frac{\log n}{\varepsilon}\right)^{f+1}\\!.$

With $f\geqslant 2$ (see Theorem 1.1), all the terms are at most the
$\widetilde{O}(n^{2}/\lambda)\cdot O(\log n/\varepsilon)^{f+1}$ for the old
FT-trees. Again, the $\widetilde{O}(nL^{2f+o(1)}/\lambda)$ space to store the
regular pivots in the sparse balls will be irrelevant.

A straightforward generalization of Lemma 5.8 shows that evaluating
$FT_{\lambda}(b_{u},b_{v})$ with query set $F$ takes time
$\widetilde{O}(L^{o(1)}(\lambda+1/\varepsilon))$.

Computing $w^{\prime}_{H^{F}}(u,v)$. Let again $G_{1},\ldots,G_{\kappa}$ be
the graphs in the leaves of the sampling trees (Section 4.2). For every
$G_{i}$ and vertex $x\in V$ for which $|\mbox{\rm
ball}_{G_{i}}(x,\lambda)|>L^{f}$, we said we store a marker. More precisely,
we associate with $(G_{i},x)$ a _single_ new pivot
$b_{x}\in\mathcal{B}\cap\mbox{\rm ball}_{G_{i}}(x,\lambda)$. As before, let
$i_{1},\dots,i_{r}$ be the indices of graphs $G_{i_{j}}$ that are relevant for
the query $(u,v,F)$. Even if $\mbox{\rm ball}_{G-F}(u,\lambda)$ and $\mbox{\rm
ball}_{G-F}(v,\lambda)$ are dense, it might be that all the $\mbox{\rm
ball}_{G_{i_{j}}}(u,\lambda)$ are sparse or all $\mbox{\rm
ball}_{G_{i_{j}}}(v,\lambda)$ are sparse. If so, we compute
$w^{\prime}_{H^{F}}(u,v)$ (and in turn $w_{H^{F}}(u,v)$) via Equation 1.
Otherwise, there are indices $i_{u},i_{v}\in\\{i_{1},\ldots,i_{r}\\}$ such
that both $|\mbox{\rm ball}_{G_{i_{u}}}(u,\lambda)|>L^{f}$ and $|\mbox{\rm
ball}_{G_{i_{v}}}(v,\lambda)|>L^{f}$. If there are multiple such indices, the
choice is arbitrary. Let $b_{u}\in\mathcal{B}\cap\mbox{\rm
ball}_{G_{i_{u}}}(u,\lambda)$ and let $b_{v}\in\mathcal{B}\cap\mbox{\rm
ball}_{G_{i_{v}}}(v,\lambda)$ be the stored new pivots. We define the
auxiliary weight as

(2) $w_{H^{F}}^{\prime}(u,v)=FT_{\lambda}(b_{u},b_{v},F)+2\lambda.$

This takes time $\widetilde{O}(L^{o(1)}(\lambda+1/\varepsilon))$, much less
than with sparse balls.

###  6.3. Approximation Guarantee

Towards Theorem 1.1, we have already seen that the space and preprocessing
time are dominated by the original FT-trees, when accounting for the slightly
larger $|B|=\widetilde{O}(n/\lambda)$. We also argued the query time. The plan
to prove the approximation guarantee is the same as in Section 5, which
crucially involved Lemma 5.6. We already discussed how to transfer its “first
case”, as well as the “second case” if both $\mbox{\rm ball}_{G-F}(u,\lambda)$
and $\mbox{\rm ball}_{G-F}(v,\lambda)$ are sparse. The “third case” is handled
by Lemma 5.3 together with an induction. Due to the restricted space, we focus
here on the “second case” also if the balls are dense, and how to adapt Lemma
5.6. As a first step, we generalize Lemmas 5.10 and 5.11 to FT-trees with
granularity $\lambda>0$.

###### Lemma 6.4.

Let $b_{u},b_{v}\in\mathcal{B}$, $P$ be any path between $b_{u}$ and $b_{v}$,
$e\in E(P)$, and $y$ a vertex of the edge $e$. Then,
$E(\operatorname{seg}_{\lambda}(e,P))=\\{e\\}$ or
$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\frac{\varepsilon}{36}\big{(}\min(|P[b_{u}..y]|,|P[y..b_{v}]|)-\lambda\big{)}$.

Recall that $d^{\ell}(u,v,A)$, for some $A\subseteq E$, is the length of the
shortest $\ell$-decomposable path in $G-A$.

###### Lemma 6.5.

Let $u,v\in V$ be two vertices, $A\subseteq E$ a set of edges, and
$b_{u}\in\mathcal{B}\cap\mbox{\rm ball}_{G-A}(u,\lambda)$ and
$b_{v}\in\mathcal{B}\cap\mbox{\rm ball}_{G-A}(u,\lambda)$. Let further $\ell$
be a positive integer, and $P$ the shortest $\ell$-expath with granularity
$\lambda$ between $b_{u}$ and $b_{v}$ in $G-A$. Then, for every $y\in V(P)$
with $|P[b_{u}..y]|,|P[y..b_{v}]|>\lambda$, it holds that
$|P[b_{u}..y]|\leqslant 4\cdot d^{(\ell)}(u,y,A)+\lambda$ and
$|P[y..b_{v}]|\leqslant 4\cdot d^{(\ell)}(y,v,A)+\lambda$.

We use the results to show that also Lemma 5.9 transfers to non-vanishing
granularity, but with a slight loss in the approximation. Again,
$d^{(2f+1)}_{\varepsilon/9}(u,b,F)$ is the length of the shortest
$(2f{+}1)$-decomposable $u$-$v$-path in $G-F$ that is _far away_ from all
failures.

###### Lemma 6.6.

Define $\delta=8\lambda/L$. Let $u,v\in V$ be such that both $|\mbox{\rm
ball}_{G-F}(u,\lambda)|,|\mbox{\rm ball}_{G-F}(u,\lambda)|>L^{f}$, and
$b_{u},b_{v}\in\mathcal{B}$ the associated new pivots. Let $P$ be any
$(2f{+}1)$-decomposable path between $u$ and $v$ in $G-F$ that is far away
from $F$. Then, $d_{G-F}(u,v)\leqslant
FT_{\lambda}(b_{u},b_{v},F)+2\lambda\leqslant 3|P|+\delta L$. Moreover, if the
_shortest_ $(2f{+}1)$-decomposable path between $u$ and $v$ in $G-F$ that is
far away from $F$ has more than $L$ edges, then,
$FT_{\lambda}(b_{u},b_{v},F)+2\lambda\leqslant(3+\delta)\cdot
d^{(2f+1)}_{\varepsilon/9}(u,v,F)$.

###### Proof.

We prove the survival of $P$ all the way to the output node $\nu^{*}$ of
$FT_{\lambda}(b_{u},b_{v})$ when queried with set $F$, as in Lemma 5.9 We have
to take care of the fact that $P$ and $P_{\nu^{*}}$ may have different
endpoints. In fact, we argue about a longer path. Let $P(b_{u},u,F)$ be the
replacement path between $b_{u}$ and $u$ in $G{-}F$. $P(b_{u},u,F)$ has at
most $\lambda$ edges by the choice $b_{u}\in\mbox{\rm ball}_{G-F}(u,\lambda)$,
same for $P(v,b_{v},F)$. Also $P$ is $(2f{+}1)$-decomposable, thus
$Q=P(b_{u},u,F)\circ P\circ P(v,b_{v},F)$ is an $(2f{+}1)$-expath with
granularity $\lambda$. We argue by induction that $Q$ exists in the graph
$G-A_{\nu}$ for every visited node $\nu$. This is clear for the root. For a
non-output node $\nu\neq\nu^{*}$, let $\nu^{\prime}$ be its visited child.

To reach a contradiction, assume $Q$ does not exist in $G-A_{\nu^{\prime}}$
Thus, there is a segment of $P_{\nu}$ that contains both a failing edge of $F$
and an edge of $Q$. Without loosing generality, we choose $e_{F}\in F$ and
$e_{Q}\in E(Q)$ such that both $e_{F}$ and $e_{Q}$ are in $P_{\nu}$ and the
subpath of $P_{\nu}$ containing both edges contains no other failing edge. Let
$y\in e_{Q}$ the endpoint closer to $e_{F}$ along $P_{\nu}$, and let $z\in
e_{F}$ the endpoint closer to $e_{Q}$. The subpath $P_{\nu}[y..z]$ is entirely
in $G-F$.

It must be that $e_{F}\neq e_{Q}$ as $Q$ lies in $G-F$. Segments with more
than one edge only appear in the middle part of the stored expath,
$|P_{\nu}[b_{u}..y]|,|P_{\nu}[y..b_{v}]|>\lambda$. By Lemmas 6.4 and 6.5, this
means

$\displaystyle|\operatorname{seg}_{\lambda}(e_{F},P)|\leqslant\frac{\varepsilon}{36}\Big{(}\min\\!\big{(}|P[b_{u}..y]|,|P[y..b_{v}]|\big{)}-\lambda\Big{)}$
$\displaystyle\quad\leqslant\frac{\varepsilon}{36}\Big{(}\min\\!\big{(}4\hskip
1.00006ptd^{(2f+1)}(u,y,A_{\nu})+\lambda,4\hskip
1.00006ptd^{(2f+1)}(y,v,A_{\nu})+\lambda\big{)}-\lambda\Big{)}$
$\displaystyle\quad=\frac{\varepsilon}{9}\min\\!\big{(}d^{(2f+1)}(u,y,A_{\nu}),d^{(2f+1)}(y,v,A_{\nu})\big{)}.$

Subpaths of expaths with granularity are again expaths with granularity (the
components $P_{a},P_{c}$ in Definition 6.3 can be empty). The subpath
$P_{\nu}[b_{u}..y]$ (resp. $P_{\nu}[y..b_{v}]$) is the _shortest_
$(2f{+}1)$-expath with granularity $\lambda$ from $b_{u}$ to $y$ (from $y$ to
$b_{v}$) in $G-A_{\nu}$. By induction $Q$ exists in $G-A_{\nu}$. $Q[b_{u}..y]$
(resp. $Q[y..b_{v}]$) is _some_ $(2f{+}1)$-expath. Together with
$|P_{\nu}[b_{u}..y]|,|P_{\nu}[y..b_{v}]|>\lambda$, this shows that $y$ must
also lie in the middle part of $Q$, that is, in $P$. Moreover $P$ is some
$(2f{+}1)$-decomposable path from $u$ to $v$ in $G-A_{\nu}$. In other words,
$d^{(2f+1)}(u,y,A_{\nu})\leqslant|P[u,y]|$ and
$d^{(2f+1)}(y,v,A_{\nu})\leqslant|P[y..v]|$.

Since $P$ is far away from $e_{F}$, we have
$|\operatorname{seg}_{\lambda}(e_{F},P)|\geqslant|P_{\nu}[y..z]|\geqslant
d_{G-F}(y,z)>\frac{\varepsilon}{9}\min(|P[u..y]|,|P[y..b]|)$, a contradiction.

For the approximation, we focus on proving

$d_{G-F}(u,v)\leqslant
FT_{\lambda}(b_{u},b_{v},F)+2\lambda\leqslant(3{+}\delta)\cdot
d^{(2f+1)}_{\varepsilon/9}(u,v,F)$

with $\delta=8\lambda/L$ if $P$ is the _shortest_ $(2f{+}1)$-decomposable path
from $u$ to $v$ in $G-F$ and has more than $L$ edges. In particular, we have
$|P|=d^{(2f+1)}_{\varepsilon/9}(u,v,F)$. The other claim will be established
in passing.

Recall that $FT_{\lambda}(b_{u},b_{v},F)=3|P_{\nu^{*}}|$ for the output node
$\nu^{*}$, for which we determined that $3|P_{\nu^{*}}|\geqslant
d_{G-F}(b_{u},b_{v})$. By the triangle inequality, it holds that
$FT_{\lambda}(b_{u},b_{v},F)+2\lambda\geqslant
d_{G-F}(b_{u},b_{v})+d_{G-F}(u,b_{u})+d_{G-F}(b_{v},v)\geqslant d_{G-F}(u,v)$.
We have seen that $Q$ survives until $\nu^{*}$ and that $P_{\nu^{*}}$ is not
longer than $Q$. In summary,

$FT_{\lambda}(b_{u},b_{v},F)+2\lambda\leqslant 3|Q|+2\lambda\leqslant
3(|P|+2\lambda)+2\lambda\\\ \leqslant 3|P|+8\lambda=3|P|+\delta
L<(3+\delta)\,d^{(2f+1)}_{\varepsilon/9}(u,v,F).\qed$

Lastly, we only sketch the necessary changes to Lemma 5.6 to derive a
$(3+\varepsilon)$-approximation. Recall that we assume
$\Delta=3-\varepsilon>0$ to be a constant. We define
$\lambda=\frac{\Delta}{96}\varepsilon L$, which in turn implies
$\delta=\frac{\Delta}{12}\varepsilon$. In fact, any
$\delta\leqslant\frac{3-\varepsilon}{9+\varepsilon}\varepsilon$ would do as
this ensures
$\delta+(6+\delta+\varepsilon)\frac{\varepsilon}{9}\leqslant\varepsilon$. In
Lemma 5.6 we had $w_{H^{F}}(u,v)\leqslant 3\,d_{G-F}(u,v)$ if the path was
short (“first case”) or long but far away from all failures (“second case”).
We now only have $w_{H^{F}}(u,v)\leqslant(3{+}\delta)\,d_{G-F}(u,v)$ due to
the dense ball case. In the “third case”, we use the $x$-$y$-$z$-argument of
Lemma 5.3. A similar reasoning as before gives
$w_{H^{F}}(u,z)\leqslant(3{+}\delta)(1{+}\frac{\varepsilon}{9})d_{G-F}(u,y)$
(instead of $(3{+}\frac{\varepsilon}{3})\,d_{G-F}(u,y)$). The crucial part is
the chain of inequalities at the end of the proof:

$\displaystyle d_{H^{F}}(u,v)\leqslant w_{H^{F}}(u,z)+d_{H^{F}}(z,v)$
$\displaystyle\leqslant(3{+}\delta)\\!\left(1{+}\frac{\varepsilon}{9}\right)d_{G-F}(u,y)+(3{+}\varepsilon)d_{G-F}(z,v)$
$\displaystyle=(3{+}\delta)\\!\left(1{+}\frac{\varepsilon}{9}\right)d_{G-F}(u,y)+(3{+}\varepsilon)d_{G-F}(z,y)+(3{+}\varepsilon)d_{G-F}(y,v)$
$\displaystyle\leqslant(3{+}\delta)\\!\left(1{+}\frac{\varepsilon}{9}\right)d_{G-F}(u,y)+(3{+}\varepsilon)\frac{\varepsilon}{9}d_{G-F}(u,y)+(3{+}\varepsilon)d_{G-F}(y,v)$
$\displaystyle=3d_{G-F}(u,y)+\delta\cdot
d_{G-F}(u,y)+(6+\delta+\varepsilon)\frac{\varepsilon}{9}\cdot d_{G-F}(u,y)\,+$
$\displaystyle\quad\quad\quad(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(y,v)$
$\displaystyle\leqslant 3d_{G-F}(u,y)+\varepsilon\cdot
d_{G-F}(u,y)+(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(y,v)$
$\displaystyle=(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(u,v).$

The parameters of Theorem 1.1 follow from the discussion in this section and
the choices $\lambda=\frac{\Delta}{96}\varepsilon L$ and $L=n^{\alpha/(f+1)}$
in the same fashion as in Lemma 5.1. The main difference is the transition
from $L$ to $\lambda$, giving an extra $1/\varepsilon$ factor in the space and
preprocessing time, and (of course) the improved query time.

###### Acknowledgements.

The authors thank Merav Parter for raising the question of designing distance
sensitivity oracles that require only subquadratic space.  This project
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation program, grant agreement No.
803118 “The Power of Randomization in Uncertain Environments (UncertainENV)”
and grant agreement No. 101019564 “The Design and Evaluation of Modern Fully
Dynamic Data Structures (MoDynStruct)”.

## References

  * (1)
  * Afek et al. (2002) Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, and Michael Merritt. 2002\.  Restoration by Path Concatenation: Fast Recovery of MPLS Paths.  _Distributed Computing_ 15 (2002), 273–283.  https://doi.org/10.1007/s00446-002-0080-6
  * Alon et al. (2019) Noga Alon, Shiri Chechik, and Sarel Cohen. 2019.  Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. In _Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP)_. 12:1–12:14.  https://doi.org/10.4230/LIPIcs.ICALP.2019.12
  * Baswana and Khanna (2013) Surender Baswana and Neelesh Khanna. 2013.  Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs.  _Algorithmica_ 66 (2013), 18–50.  https://doi.org/10.1007/s00453-012-9621-y
  * Bender and Farach-Colton (2000) Michael A. Bender and Martín Farach-Colton. 2000.  The LCA Problem Revisited. In _Proceedings of the 4th Latin American Symposium Theoretical Informatics (LATIN)_. 88–94.  https://doi.org/10.1007/10719839_9
  * Bernstein and Karger (2008) Aaron Bernstein and David R. Karger. 2008.  Improved Distance Sensitivity Oracles via Random Sampling. In _Proceedings of the 19th Symposium on Discrete Algorithms (SODA)_. 34–43.  https://dl.acm.org/doi/abs/10.5555/1347082.1347087
  * Bernstein and Karger (2009) Aaron Bernstein and David R. Karger. 2009.  A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges. In _Proceedings of the 41st Symposium on Theory of Computing (STOC)_. 101–110.  https://doi.org/10.1145/1536414.1536431
  * Bilò et al. (2022) Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2022\.  Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In _Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP)_. 22:1–22:19.  https://doi.org/10.4230/LIPIcs.ICALP.2022.22
  * Bilò et al. (2021a) Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2021a.  Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In _Proceedings of the 29th European Symposium on Algorithms (ESA)_. 18:1–18:17.  https://doi.org/10.4230/LIPIcs.ESA.2021.18
  * Bilò et al. (2021b) Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2021b.  Space-Efficient Fault-Tolerant Diameter Oracles. In _Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS)_. 18:1–18:16.  https://doi.org/10.4230/LIPIcs.MFCS.2021.18
  * Bodwin et al. (2021) Greg Bodwin, Michael Dinitz, and Caleb Robelle. 2021\.  Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. In _Proceedings of the 32nd Symposium on Discrete Algorithms (SODA)_. 2924–2938.  https://doi.org/10.1137/1.9781611976465.174
  * Bodwin et al. (2022) Greg Bodwin, Michael Dinitz, and Caleb Robelle. 2022\.  Partially Optimal Edge Fault-Tolerant Spanners. In _Proceedings of the 33rd Symposium on Discrete Algorithms (SODA)_. 3272–3286.  https://doi.org/10.1137/1.9781611977073.129
  * Cabello et al. (2013) Sergio Cabello, Erin W. Chambers, and Jeff Erickson. 2013\.  Multiple-Source Shortest Paths in Embedded Graphs.  _SIAM J. Comput._ 42 (2013), 1542–1571.  https://doi.org/10.1137/120864271
  * Chechik and Cohen (2020) Shiri Chechik and Sarel Cohen. 2020.  Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time. In _Proccedings of the 52nd Symposium on Theory of Computing (STOC)_. 1375–1388.  https://doi.org/10.1145/3357713.3384253
  * Chechik et al. (2017) Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. 2017\.  ($1{+}\varepsilon$)-Approximate $f$-Sensitive Distance Oracles. In _Proceedings of the 28th Symposium on Discrete Algorithms (SODA)_. 1479–1496.  https://doi.org/10.1137/1.9781611974782.96
  * Chechik et al. (2010) Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. 2010.  Fault Tolerant Spanners for General Graphs.  _SIAM J. Comput._ 39 (2010), 3403–3423.  https://doi.org/10.1137/090758039
  * Chechik et al. (2012) Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. 2012.  $f$-Sensitivity Distance Oracles and Routing Schemes.  _Algorithmica_ 63 (2012), 861–882.  https://doi.org/10.1007/s00453-011-9543-0
  * Demetrescu and Thorup (2002) Camil Demetrescu and Mikkel Thorup. 2002.  Oracles for Distances Avoiding a Link-Failure. In _Proceedings of the 13th Symposium on Discrete Algorithms (SODA)_. 838–843.  https://dl.acm.org/doi/10.5555/545381.545490
  * Demetrescu et al. (2008) Camil Demetrescu, Mikkel Thorup, Rezaul A. Chowdhury, and Vijaya Ramachandran. 2008.  Oracles for Distances Avoiding a Failed Node or Link.  _SIAM J. Comput._ 37 (2008), 1299–1318.  https://doi.org/10.1137/S0097539705429847
  * Duan and Pettie (2009) Ran Duan and Seth Pettie. 2009.  Dual-Failure Distance and Connectivity Oracles. In _Proceedings of the 20th Symposium on Discrete Algorithms (SODA)_. 506–515.  https://dl.acm.org/doi/10.5555/545381.545490
  * Duan and Ren (2022) Ran Duan and Hanlin Ren. 2022.  Maintaining Exact Distances under Multiple Edge Failures. In _Proceedings of the 54th Symposium on Theory of Computing (STOC)_. 1093–1101.  https://doi.org/10.1145/3519935.3520002
  * Erdős (1964) Paul Erdős. 1964\.  Extremal Problems in Graph Theory.  _Theory of Graphs and its Applications_ (1964), 29–36.
  * Grandoni and Vassilevska Williams (2020) Fabrizio Grandoni and Virginia Vassilevska Williams. 2020\.  Faster Replacement Paths and Distance Sensitivity Oracles.  _ACM Transaction on Algorithms_ 16 (2020), 15:1–15:25.  https://doi.org/10.1145/3365835
  * Gu and Ren (2021) Yong Gu and Hanlin Ren. 2021.  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)_. 76:1–76:20.  https://doi.org/10.4230/LIPIcs.ICALP.2021.76
  * Hagerup et al. (2001) Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh. 2001\.  Deterministic Dictionaries.  _Journal of Algorithms_ 41 (2001), 69–85.  https://doi.org/10.1006/jagm.2001.1171
  * Karthik C.S. and Parter (2021) Karthik C.S. and Merav Parter. 2021.  Deterministic Replacement Path Covering. In _Proceedings of the 32nd Symposium on Discrete Algorithms (SODA)_. 704–723.  https://doi.org/10.1137/1.9781611976465.44
  * Levcopoulos et al. (1998) Christos Levcopoulos, Giri Narasimhan, and Michiel H. M. Smid. 1998\.  Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners. In _Proceedings of the 30th Symposium on Theory of Computing (STOC)_. 186–195.  https://doi.org/10.1145/276698.276734
  * Ren (2022) Hanlin Ren. 2022\.  Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.  _J. Comput. System Sci._ 123 (2022), 159–170.  https://doi.org/10.1016/j.jcss.2021.08.005
  * Roditty and Zwick (2012) Liam Roditty and Uri Zwick. 2012.  Replacement Paths and $k$ Simple Shortest Paths in Unweighted Directed Graphs.  _ACM Transaction on Algorithms_ 8, Article 33 (2012), 33:1–33:11 pages.  https://doi.org/10.1145/2344422.2344423
  * Thorup and Zwick (2005) Mikkel Thorup and Uri Zwick. 2005.  Approximate Distance Oracles.  _J. ACM_ 52 (2005), 1–24.  https://doi.org/10.1145/1044731.1044732
  * Weimann and Yuster (2013) Oren Weimann and Raphael Yuster. 2013.  Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication.  _ACM Transactions on Algorithms_ 9 (2013), 14:1–14:13.  https://doi.org/10.1145/2438645.2438646

##  Appendix A Omitted Proofs

###  A.1. Proofs Omitted from Section 4

See 4.2

###### Proof.

Assume that $F\cap S_{y}\subseteq A_{y}$ holds, that is, $y$ satisfies Item 1,
and let $x_{1},\ldots,x_{K}$ be the child nodes of $y$. Each edge of $A_{y}$
is sampled for $A_{x}$ with probability $p$. The probability that there exists
some child $x_{j}$ satisfying $F\cap S_{y}\subseteq A_{x_{j}}$ is therefore

$\displaystyle 1-\prod_{j=1}^{K}\operatorname{P}\\!\Big{[}F\cap
S_{y}\nsubseteq A_{x_{j}}\Big{]}$
$\displaystyle=1-\prod_{i=1}^{K}\left(1-p^{|F\cap S_{y}|}\right)$
$\displaystyle=1-\left(1-\frac{1}{K^{|F\cap S_{y}|/f}}\right)^{K}$
$\displaystyle\geqslant 1-\left(1-\frac{1}{K}\right)^{K}\geqslant
1-\frac{1}{e}.$

For the second statement, let $r{-}1$ be the depth of $y$ in $T_{i}$. Recall
that the path $P=P_{s,t,G-F}$ has at most $(2k{-}1)L$ edges. By our assumption
of $y$ satisfying Item 2, at most $K^{\frac{h-r+1}{f}}$ of those are in
$A_{y}$. Let $x$ be a child of $y$. We first analyze the case that $x$ is a
leaf, that is, we have $r=h$.

$\displaystyle\operatorname{P}\\!\Big{[}E(P)\cap A_{x}=\emptyset\Big{]}$
$\displaystyle=(1-p)^{|E(P)\cap
A_{y}|}=\left(1-\frac{1}{K^{1/f}}\right)^{|E(P)\cap A_{y}|}$
$\displaystyle\geqslant\left(1-\frac{1}{K^{1/f}}\right)^{K^{1/f}}\geqslant\frac{1}{4}.$

Now suppose $r<h$. Observe that the random variable $X=|E(P)\cap A_{x}|$
follows the binomial distribution with parameters $|E(P)\cap A_{y}|$ and $p$.
In particular, it holds that $\operatorname{E}[X]\leqslant
pK^{\frac{h-r+1}{f}}=K^{\frac{h-r}{f}}$. By the central limit theorem, we have
$\operatorname{P}\\!\big{[}X\geqslant
K^{\frac{h-r}{f}}\big{]}\leqslant\operatorname{P}\\!\big{[}X\geqslant\operatorname{E}[X]\hskip
1.00006pt\big{]}\leqslant\frac{3}{4}$. In both cases, we see that $x$
satisfies Item 2 with probability at least $\frac{1}{4}$.

We now turn to the third clause of the lemma. Suppose $y$ is well-behaved and
its child node $x$ fulfills Items 1 and 2. If $x$ is a leaf, it is well-
behaved deterministically. Indeed, in this case, subgraph $S_{x}$ is just the
Thorup-Zwick spanner for $S_{y}-A_{x}$. Item 1 for $x$ means that
$S_{y}-A_{x}$ doesn’t contain edges of $F$. Likewise, $x$ satisfying Item 2
with $r=h$ and together with $y$ satisfying Item 3 shows that the path $P$ is
contained in $S_{y}-A_{x}$. The inheritance property (Lemma 4.1) applied to
$G^{\prime}=G-F$ and $H=S_{y}-A_{x}$ gives that $P$ is indeed contained in
$S_{x}$.

For $r<h$, this argument goes through only with a certain probability. Recall
that the graph $S_{x}$ is obtained in $J_{r}=4K^{h-r}$ iterations, wherein, in
each iteration, a subset $A\subseteq A_{x}$ is sampled by selecting each edge
with probability $p^{h-r}$, and the spanner $H_{A}$ of $S_{y}{-}A$ is
computed. $S_{x}$ is the union of all $4K^{h-r}$ $H_{A}$’s. We estimate the
probability that the path $P$ exists in $S_{y}-A$ and no failing edge of $F$
is in $S_{y}{-}A$, which, by inheritance to $H_{A}$ and taking the union, will
imply $P$ lies in $S_{x}$.

We first claim that
$\operatorname{P}[F\cap(E(S_{y}){\setminus}A)=\emptyset]=p^{|F\cap
E(S_{y})|\cdot(h-r)}$. To see this, note that Item 1 holding for $x$ means
that $F\cap S_{y}\subseteq A_{x}$. No failure from $F$ is in $S_{y}{-}A$ if
and only if all the edges of $F\cap S_{y}$ are chosen for $A$. Our second
claim is $\operatorname{P}[E(P)\subseteq
E(S_{y}){\setminus}A]=(1-p^{h-r})^{|E(P)\cap A_{x}|}$. It holds that
$E(P)\subseteq E(S_{y})$ since $y$ is well-behaved (Item 3). Thus,
$E(P)\subseteq E(S_{y}){\setminus}A$ is true if and only if none of the edges
in $E(P)\cap A_{x}$ are selected in $A$.

Using the independence of the events and the Item 2 of the node $x$, we arrive
at

$\displaystyle\operatorname{P}\\!\Big{[}F\cap(E(S_{y}){\setminus}A)=\emptyset\,\wedge\,E(P)\subseteq
E(S_{y}){\setminus}A\Big{]}$ $\displaystyle\quad=p^{|F\cap
E(S_{y})|\cdot(h-r)}\cdot(1-p^{h-r})^{|E(P)\cap A_{x}|}$
$\displaystyle\quad\geqslant
p^{f(h-r)}\cdot\Big{(}1-p^{h-r}\Big{)}^{K^{\frac{h-r}{f}}}=\frac{1}{K^{h-r}}\cdot\left(1-\frac{1}{K^{\frac{h-r}{f}}}\right)^{K^{\frac{h-r}{f}}}$
$\displaystyle\quad\geqslant\frac{1}{4\cdot K^{h-r}}.$

Iterating this $J_{r}$ times gives

$\operatorname{P}\\!\big{[}E(P)\subseteq E(S_{x})\big{]}\geqslant
1-\left(1-\frac{1}{4K^{h-r}}\right)^{J_{r}}\\\
=1-\left(1-\frac{1}{4K^{h-r}}\right)^{4K^{h-r}}\geqslant 1-\frac{1}{e}.$

The assertion about the root follows as the previous one by observing that,
for the purpose of this proof, the original graph $G$ is the “parent” of the
root in that we have $A_{x}=E$ and $S_{y}=G$. ∎

###  A.2. Proof Omitted from Section 6

See 6.1

###### Proof.

Let $P=P(u,v,F)$. Without losing generality, we assume $\mbox{\rm
ball}_{G-F}(u,\lambda)$ is sparse, the other case is symmetric. Note that $P$
has at least $L\geqslant\lambda$ edges. Let $u^{\prime}\in V(P)$ be the vertex
on $P$ at distance exactly $\lambda$ from $u$. There exists a (regular) pivot
$b^{*}$ on $P[u..u^{\prime}]$ w.h.p. Here, we used the adapted sampling
probability for set $B$ in Section 6. Note that the pivot is in
$B_{G-F}(u,\lambda)=B\cap\mbox{\rm ball}_{G-F}(u,\lambda)$. The graphs
$G_{1},\dots,G_{\kappa}$ are an $(L,f)$-replacement path covering, and
Algorithm 3 finds the right indices $i_{1},\dots,i_{r}$. Equation 1 thus gives

$\displaystyle w_{H^{F}}(u,v)$ $\displaystyle\leqslant
w^{\prime}_{H^{F}}(u,v)=\min_{\begin{subarray}{c}1\leqslant j\leqslant r\\\
b\in B_{G_{i_{j}}}(u,\lambda)\end{subarray}}\left(\widehat{d^{\leqslant
L}}(u,b,F)+FT(b,v,F)\right)$ $\displaystyle\leqslant\widehat{d^{\leqslant
L}}(u,b^{*},F)+FT(b^{*},v,F).$

Recall that _FT_ approximates the length $d^{(2f+1)}_{\varepsilon/9}$ of the
shortest $(2f{+}1)$-decomposable path that is far away from all failures. As
in the proof of Lemma 5.6, since $P$ is far away from all failures,
$P[b^{*}..v]$ is $(2f{+}1)$-decomposable and far away itself. It holds that

$\displaystyle w^{\prime}_{H^{F}}(u,v)$ $\displaystyle\leqslant 3\cdot
d_{G-F}(u,b^{*})+3\cdot d^{(2f+1)}_{\varepsilon/9}(b^{*},v,F)$
$\displaystyle=3\hskip 1.00006pt|P[u..b^{*}]|+3\hskip
1.00006pt|P[b^{*}..v]|=3\hskip 1.00006pt|P|=3\hskip
1.00006ptd_{G-F}(u,v).\qed$

See 6.4

###### Proof.

If $|P|\leqslant 2\lambda$ then $\operatorname{seg}_{\lambda}(e,P)=\\{e\\}$
for every edge $e$ of $P$ by definition. We can thus assume that $P$ has more
than $2\lambda$ edges. Let $u^{\prime}$ and $v^{\prime}$ be the two vertices
of $P$ such that $|P[b_{u}..u^{\prime}]|=\lambda$ and
$|P[v^{\prime}..b_{v}]|=\lambda$, respectively. Let $e$ be an edge of $P$ such
that $\operatorname{seg}_{\lambda}(e,P)\supsetneq\\{e\\}$ and $y\in e$. Note
that $y$ must lie on $P[u^{\prime}..v^{\prime}]$ since $e$ is not among the
first or last $\lambda$ edges of $P$. It is enough to show

$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\frac{\varepsilon}{36}\cdot\min(|P[u^{\prime}..y]|,|P[y..v^{\prime}]|)$

since
$\min(|P[u^{\prime}..y]|,|P[y..v^{\prime}]|)=\min(|P[b_{u}..y]|,|P[y..b_{v}]|)-\lambda$.

Let $z$ be the vertex of the edge $e$ that is not $y$. First, assume that $y$
is closer to $u^{\prime}$ along $P$ than $z$, that is,
$|P[u^{\prime}..y]|<|P[u^{\prime}..z]|$. Let $i$ be the maximal integer such
that $(1+\varepsilon/36)^{i}\leqslant|P[u^{\prime}..y]|$, whence
$(1+\varepsilon/36)^{i+1}>|P[u^{\prime}..y]|$. Since
$\operatorname{seg}_{\lambda}(e,P)$ contains more edges than just $e$, the
endpoints $y,z$ cannot both be netpoints of the path $P$ with granularity
$\lambda$. Therefore, we even have
$(1+\varepsilon/36)^{i+1}>|P[u^{\prime}..z]|$, which gives

$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\left(1+\frac{\varepsilon}{36}\right)^{i+1}-\left(1+\frac{\varepsilon}{36}\right)^{i}\\\
=\frac{\varepsilon}{36}\cdot\left(1+\frac{\varepsilon}{36}\right)^{i}\leqslant\frac{\varepsilon}{36}\cdot|P[u^{\prime}..y]|.$

Symmetrically, we can show that
$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\varepsilon/36\cdot|P[z..v^{\prime}]|$,
from which it follows that
$|\operatorname{seg}_{\lambda}(e,P)|<\varepsilon/36|P[y..v^{\prime}]|$ since
we assumed $|P[u^{\prime}..y]|<|P[u^{\prime}..z]|$, whence
$|P[z..v^{\prime}]|<|P[y..v^{\prime}]|$.

If conversely $|P[u^{\prime}..y]|>|P[u^{\prime}..z]|$ holds (and thus
$|P[z..v^{\prime}]|>|P[y..v^{\prime}]|$), then the exact same argument as
above where $y$ and $z$ switch places shows
$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\varepsilon/36\cdot|P[u^{\prime}..z]|<\varepsilon/36\cdot|P[u^{\prime}..y]|$
and
$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\varepsilon/36\cdot|P[y..v^{\prime}]|$.
In summary, we get
$|\operatorname{seg}_{\lambda}(e,P)|\leqslant\varepsilon/36\cdot\min(|P[u^{\prime}..y]|,|P[y..v^{\prime}]|)$
in both cases. ∎

See 6.5

###### Proof.

We only show that $|P[b_{u}..y]|,|P[y..b_{v}]|>\lambda$ implies
$|P[b_{u}..y]|\leqslant 4\hskip 1.00006ptd^{(\ell)}(u,y,A)+\lambda$, the proof
of the other inequality is symmetric. Let $P^{(\ell)}_{G-A}(u,y)$ be the
shortest $\ell$-decomposable $u$-$y$-path in $G-A$, that is,
$d^{(\ell)}(u,y,A)=|P^{(\ell)}_{G-A}(u,y)|$. For the sake of contradiction,
assume $|P[b_{u}..y]|-\lambda>4|P^{(\ell)}_{G-A}(u,y)|$. Let $P_{b_{u}}$ be
the shortest path in $G-A$ from $b_{u}$ to $u$. Since
$b_{u}\in\mathcal{B}\cap\mbox{\rm ball}_{G-A}(u,\lambda)$, it holds that
$|P_{b_{u}}|\leqslant\lambda$.

We first prove that $P^{\prime}=P_{b_{u}}\circ P^{(\ell)}_{G-A}[u..y]\circ
P[y..b_{v}]$ is an $\ell$-expath with granularity $\lambda$. Let $P=P_{a}\circ
P_{b}\circ P_{c}$ be the constituting decomposition of $P$ as an expath with
granularity. That means $P_{a}$ and $P_{c}$ contain at most $\lambda$ edges
each, while $P_{b}$ is the concatenation $P_{0}\circ\ldots\circ
P_{2\log_{2}n}$ of $2\log_{2}(n)+1$, $\ell$-decomposable paths such that
$|P_{i}|\leqslant\min(2^{i},2^{2\log_{2}n-i})$. To show that $P^{\prime}$ is
an $\ell$-expath with granularity $\lambda$, we define $\ell$-decomposable
paths $P^{\prime}_{0},\ldots,P^{\prime}_{2\log n}$ in $G-A$ such that
$|P^{\prime}_{i}|\leqslant\min(2^{i},2^{2\log_{2}n-i})$ and $P^{\prime}$ is
the concatenation of $P_{b_{u}}\circ P^{\prime}_{0}\circ\ldots\circ
P^{\prime}_{2\log n}\circ P_{c}$.

We have $|P[b_{u}..y]|>\lambda$ and thus $|P[b_{u}..y]|-|P_{a}|\geqslant 1$.
Let $j_{0}=\lfloor\log_{2}(|P[b_{u}..y]|-|P_{a}|)\rfloor-1$. Be aware that
$j_{0}=-1$ is possible. Since $|P_{i}|\leqslant 2^{i}$, we have

$|P_{a}|+\sum_{i=0}^{j_{0}}|P_{i}|<|P_{a}|+2^{j_{0}+1}\leqslant|P_{a}|+|P[b_{u}..y]|-|P_{a}|=|P[b_{u}..y]|.$

This implies that either $y$ is contained in a subpath $P_{j_{1}}$ of $P_{b}$
for some $j_{1}>j_{0}$ or that $y$ is a vertex of $P_{c}$. The latter case is
impossible as $|P_{c}|\leqslant\lambda$ while $|P[y..b_{v}]|>\lambda$. So $y$
is indeed on $P_{j_{1}}$.

We are now ready to define the new subpaths
$P^{\prime}_{0},P^{\prime}_{1},\ldots,P^{\prime}_{2\log_{2}n}$. For every
$0\leqslant i<j_{0}$, we define $P^{\prime}_{i}$ as the empty path, and set
$P^{\prime}_{j_{0}}=P^{(\ell)}_{G-A}(u,y)$. For every $j_{0}<i<j_{1}$, we
define $P^{\prime}_{i}$ as the empty path again, and $P^{\prime}_{j_{1}}$ is
the suffix of $P_{j_{1}}$ starting at $y$. Finally, for every $i>j_{1}$, we
set $P^{\prime}_{i}=P_{i}$. Clearly all the $P^{\prime}_{i}$ are
$\ell$-decomposable paths in $G-A$. The only index where the length bound is
possibly in doubt is $j_{0}$. We need to prove that
$|P^{(\ell)}_{G-A}(u,y)|\leqslant\min(2^{j_{0}},2^{2\log_{2}n-{j_{0}}})$. Note
that $j_{0}<\log_{2}n$ as otherwise $|P[b_{u}..y]|-|P_{a}|>n$, thus

$\displaystyle\min(2^{j_{0}},2^{2\log_{2}n-{j_{0}}})$
$\displaystyle=2^{j_{0}}=2^{\lfloor\log(|P[b_{u}..x]|-|P_{a}|)\rfloor-1}$
$\displaystyle\geqslant\frac{|P[b_{u}..x]|-|P_{a}|}{4}\geqslant\frac{|P[b_{u}..x]|-\lambda}{4}$
$\displaystyle>|P^{(\ell)}_{G-A}(u,y)|.$

The last step uses the assumption $|P[b_{u}..y]|-\lambda>4\hskip
1.00006pt|P^{(\ell)}_{G-A}(u,y)|$.

We have established that $P^{\prime}=P_{b_{u}}\circ
P^{(\ell)}_{G-A}[u..y]\circ P[y..b_{v}]$ is some $\ell$-expath with
granularity $\lambda$ from $b_{u}$ to $b_{v}$ in $G-A$. However, its length is

$\displaystyle|P^{\prime}|$
$\displaystyle=|P_{b_{u}}|+|P^{(\ell)}_{G-A}(u,y)|+|P[y..b_{v}]|$
$\displaystyle<\lambda+\frac{|P[b_{u}..y]|-\lambda}{4}+|P[y..b_{v}]|=\frac{3\lambda+|P[b_{u}..y]|}{4}+|P[y..b_{v}]|$
$\displaystyle<|P[b_{u}..y]|+|P[y..b_{v}]|=|P|,$

where the last inequality follows from $|P[b_{u}..y]|>\lambda$. This is a
contradiction to $P$ being the shortest $\ell$-expath with granularity
$\lambda$ from $b_{u}$ to $b_{v}$ in $G-A$. ∎

###### Lemma A.1.

With the changes made in Section 6, and when setting
$\lambda=\frac{3-\varepsilon}{96}\varepsilon L$ and
$\delta=\frac{8\lambda}{L}$, the inequalities $d_{G-F}(s,t)\leqslant
d_{H^{F}}(s,t)\leqslant(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(s,t)$ hold
with high probability.

###### Proof.

The structure of the proof is very similar to Lemma 5.6. Recall the definition
of the graph $H^{F}$ given a query $(s,t,F)$. It has an edge for every pair in
$\binom{V(F)\cup\\{s,t\\}}{2}$ and the weight $w_{H^{F}}(u,v)$ is the minimum
of $\widehat{d^{\leqslant L}}(u,v,F)$ and $w^{\prime}_{H^{F}}(u,v)$, where the
computation of the latter depends on whether we are in the sparse ball case or
the dense ball case. The details are given in Equations 1 and 2

The first inequality $d_{G-F}(s,t)\leqslant d_{H^{F}}(s,t)$ again follows from
the fact that the oracle calls used to compute $w_{H^{F}}(u,v)$ never
underestimate the true replacement distance $d_{G-F}(u,v)$.

The second one will follow from
$d_{H^{F}}(u,v)\leqslant(3{+}\varepsilon)\hskip 1.00006ptd_{G-F}(u,v)$ holding
for all pairs, which in turn is shown by induction over the replacement
distance. Consider a pair $u,v\in V(H^{F})$ and assume the statement holds for
all pairs of vertices with smaller distance. We distinguish the same three
cases as before, beginning with the replacement path $P=P(u,v,F)$ having at
most $L$ edges. The same argument as before, using Theorem 1.2, gives
$d_{H^{F}}(u,v)\leqslant 3\hskip 1.00006ptd_{G-F}^{\leqslant L}(u,v)=3\hskip
1.00006ptd_{G-F}(u,v)\leqslant(3+\varepsilon)\hskip 1.00006ptd_{G-F}(u,v)$
w.h.p.

In the second case, $P$ is long and far away from all failures. If $\mbox{\rm
ball}_{G-F}(u,\lambda)$ or $\mbox{\rm ball}_{G-F}(v,\lambda)$ contain at most
$L^{f}$ vertices, then Lemma 6.1 also shows that $d_{H^{F}}(u,v)\leqslant
w_{H}^{F}(u,v)\leqslant 3\cdot d_{G-F}(u,v)$. For the subcase that $|\mbox{\rm
ball}_{G-F}(u,\lambda)|,|\mbox{\rm ball}_{G-F}(v,\lambda)|>L^{f}$, recall that
$\delta=8\lambda/L=\frac{3-\varepsilon}{12}\varepsilon$ and that
$d_{\varepsilon/9}^{(2f+1)}(u,v,F)$ is the length of the shortest
$(2f{+}1)$-decomposable $u$-$v$-path in $G-F$ that is far away from $F$. The
replacement path $P$ is $f$-decomposable and therefore also
$(2f{+}1)$-decomposable. It is far away by assumption, so we get
$d_{\varepsilon/9}^{(2f+1)}(u,v,F)=|P|=d_{G-F}(u,v)$. The second part of Lemma
6.6 now implies that $d_{H^{F}}(u,v)\leqslant
w^{\prime}_{H^{F}}(u,v)\leqslant(3+\delta)\cdot
d_{G-F}(u,v)\leqslant(3+\varepsilon)\cdot d_{G-F}(u,v)$.

The main part of the proof consists in recovering the third case, where the
replacement path $P$ is long but not far away from $F$. By Lemma 5.3, there
are vertices $x\in\\{u,v\\}$, $y\,{\in}\,V(P)$, and
$z\,{\in}\,\operatorname{tr}^{\varepsilon/9}_{G-F}(P)\cap V(F)$ such that
$d_{G-F}(z,y)\leqslant\tfrac{\varepsilon}{9}\,{\cdot}\,d_{G-F}(x,y)$ and the
path $P^{\prime}=P[x..y]\circ P(y,z,F)$ is far away. $P(y,z,F)$ denotes the
shortest path from $y$ to $z$ in $G-F$. The length of $P^{\prime}$ is bounded
from above by $(1+\tfrac{\varepsilon}{9})\cdot d_{G-F}(x,y)$.

We again assume $x=u$ for simplicity. Just as before, if $P^{\prime}$ has at