# Nearly Optimal Fault Tolerant Distance Oracle

Dipan Dey
IIT Gandhinagar
Gandhinagar
India
<EMAIL_ADDRESS>
Manoj Gupta
IIT Gandhinagar
Gandhinagar
India
<EMAIL_ADDRESS>

###### Abstract

We present an $f$-fault tolerant distance oracle for an undirected weighted
graph where each edge has an integral weight from $[1\dots W]$. Given a set
$F$ of $f$ edges, as well as a source node $s$ and a destination node $t$, our
oracle returns the _shortest path_ from $s$ to $t$ avoiding $F$ in
$O((cf\log(nW))^{O(f^{2})})$ time, where $c>1$ is a constant. The space
complexity of our oracle is $O(f^{4}n^{2}\log^{2}(nW))$. For a constant $f$,
our oracle is nearly optimal both in terms of space and time (barring some
logarithmic factor).

##  1 Introduction

In real-life networks, which can be represented as graphs, determining the
distance between any two vertices is often necessary. This problem is commonly
known as the “all-pair shortest path” problem in the literature. In the data
structure version of this problem, the goal is to preprocess the graph to
answer distance queries between any two vertices efficiently.

$\textsc{Query}(s,t)$: Find the weight of the shortest path from $s$ to $t$.

For unweighted graphs, the shortest path between all pairs of vertices can be
found using the breadth-first search (BFS) algorithm, and the information can
be stored in $O(n^{2})$ space. The query time is $O(1)$. In the case of
weighted graphs, there is extensive research on all-pair shortest path
algorithms[Flo67, War62, Fre76, Dob90, Tak92, Han04, Tak04, Zwi04, Tak05,
Cha05, Han06, Cha07, Han08, Cha08, Wil14]. Using the state-of-the-art
algorithm, we can construct a data structure of size $O(n^{2})$ with $O(1)$
query time.

However, real-life networks are prone to failures. Thus, we need to find the
distance between vertices, avoiding certain edges or vertices, known as faults
in the literature. This paper focuses on edge faults. Let’s formally define
the problem. We are given an undirected weighted graph $G$. We can preprocess
$G$ and construct some suitable data structures. These data structures are
used to answer queries of the form:

$\textsc{Query}(s,t,F)$: Find the shortest path (and its weight) from $s$ to
$t$ avoiding the edge set $F$.

The algorithm that handles the aforementioned query is known as the query
algorithm. It utilises the prepared data structures to respond to the query.
This combination of data structures and the query algorithm is referred to as
a distance oracle in the literature. Since we are dealing with faults, our
oracle is known as $f$-fault-tolerant distance oracle when $|F|\leq f$. A
fault-tolerant distance oracle is evaluated based on its size, query time (the
time required to answer a query), and the number of faults it can handle,
i.e., the maximum size of $F$. In a naive approach, we could store all
distances, avoiding all possible faults and return the distance upon query.
However, this would consume significant space, albeit with a small query time.
Hence, the primary research challenge in this field is to reduce the space
while not significantly increasing the query time.

Faults |  Space | Query time |  Remarks | Reference
---|---|---|---|---
$1$ |  $\tilde{O}(n^{2})$ | $O(1)$ |  $\tilde{O}$ hides poly$\log n$ factor. | [DTCR08]
$2$ |  $\tilde{O}(n^{2})$ | $O(\log n)$ |  - | [DP09]
$f$ |  $\tilde{O}(n^{3-\alpha})$ | $\tilde{O}(n^{2-(1-\alpha)/f})$ |  $\alpha\in[0,1]$ when the preprocessing time is $O(Wn^{3.376-\alpha})$ and edge weights are integral and in the range $[-W\dots W].$ | [WY13]
$f$ |  $\tilde{O}(Wn^{2+\alpha})$ | $O(Wn^{2-\alpha}f^{2}+Wnf^{\omega})$ |  $\alpha\in[0,1]$, edge weights are integral and in the range $[-W\dots W]$ and $\omega$ is the matrix multiplication exponent [CW87, Sto10, Wil12, Gal14, AW21] | [vdBS19]
$f$ |  $O(n^{4})$ | $O(f^{O(f)})$ |  - | [DR22]
$f$ |  $O(n^{2})$ | $\tilde{O}(nf)$ |  Edge weights are in the range $[1\dots W]$ | [KS23]
Table 1:  Relevant results for fault-tolerant distance oracle

We summarise relevant results in this area in Table 1. When $f=1$, the oracle
presented in [DTCR08] is optimal. For $f=2$, Duan and Pettie [DP09] designed a
nearly optimal distance oracle (barring some poly$\log n$ factor). However,
for $f>2$, our understanding of this problem is limited. The results can be
categorised into two groups: those with high query time but low space [WY13,
vdBS19, KS23], and those with low query time but high space [DR22]. An
important question in this field is to develop an oracle that minimises both
space (as in [KS23]) and query time (as in [DR22]). In fact, this question is
explicitly raised in [DR22], and we quote it here (with minor notation
changes). [font=itshape, begintext=“Problem 1: , endtext=”[DR22]] Fix a large
constant $f$. Is there an $f$-failure oracle for handling exact distance
queries in undirected graphs with query time poly($\log n,\log W$) and a
reasonable size bound? We answer this question in the affirmative. The main
result of our paper is:

######  Theorem 1.1.

There is an $f$-fault-tolerant distance oracle that takes
$O(f^{4}n^{2}\log(nW))$ space and has a query time of
$O(c^{(f+1)^{2}}f^{8(f+1)^{2}}\log^{2(f+1)^{2}}(nW))$, where $c>1$ is a
constant. Moreover, the oracle returns a path in $(f+1)$-decomposable form.

In the above theorem, we have used the term “$(f+1)$-decomposable form”. We
will describe this term now without delving into technical details. Most of
the existing fault-tolerant distance oracles return the weight of the shortest
path, not the path itself. If they do return the shortest path, their query
time becomes $\Omega(n)$. However, our algorithm returns the shortest path
while avoiding $F$ in $o(n)$ time. One might wonder if the output size could
be as large as $O(n)$, how can we claim a query time independent of $n$. We
will demonstrate that the shortest path from $s$ to $t$, avoiding $F$, can be
represented in a suitable form of size $O(f)$. This form is termed as
$(f+1)$-decomposable form. We will formally define this term in Section 2.

For a fixed $f$, compared to [DR22], our oracle has better space and compared
to [WY13, vdBS19, KS23], it has a better query time. In fact, for a fixed $f$,
our oracle is nearly optimal both in terms of space and time (barring some
poly$\log(nW)$ factor). Also note that the results in [vdBS19, KS23] have a
linear dependency on $W$ in terms of space and/or query time, while our result
has a polylog dependency on $W$. One drawback of our result compared to [WY13,
vdBS19] is that it works for graphs with weights $[1\dots W]$ as opposed to
$[-W\dots W]$. Another drawback is that the preprocessing time (approximately
$\Omega(n^{f})$) of our oracle is huge.

###  1.1 Related works

Single fault tolerant distance oracle, $f=1$: Demetrescu et al.[DTCR08]
designed a single fault tolerant distance oracle in $O(mn^{2}+n^{3}\log n)$
construction/preprocessing time (the time required to construct the oracle
before taking any query) with $\tilde{O}(n^{2})$ space and $O(1)$ query time.
Bernstein and Karger[BK08] improved the preprocessing time to
$\tilde{O}(n^{2}\sqrt{m})$ and later to $\tilde{O}(mn)$ time in [BK09a]. The
preprocessing times of the above results are $\Omega(n^{3})$. Grandoni and
Williams [GW19] designed the first single fault tolerant distance oracle with
subcubic preprocessing time and sublinear query time. Chechik and Cohen [CC20]
kept the preprocessing time as subcubic but improved the query time to
$\tilde{O}(1)$. After that, Gu and Ren [GR21] constructed a single fault
tolerant distance oracle with $O(n^{2.6146}M)$ preprocessing time and constant
query time where $M$ is the maximum edge weight.

Fault tolerant approximate distance oracle: Another direction of work is
approximate fault tolerant distance oracle. Here, instead of reporting the
exact distance, the oracle returns the approximate distance between two
vertices in the presence of faults. Baswana and Khanna [BK13] designed
$(2k-1)(1+\epsilon)$-approximation distance oracle with
$O(kn^{1+1/k}\log^{3}n/{\epsilon}^{4})$ (where $k>1$). For multiple faults,
Chechik et al.[CCFK17] designed a $(1+\epsilon)$-approximate distance oracle
which handled upto $f=o(\frac{\log n}{\log\log n})$ many faults. However,
their algorithm had a super quadratic space requirement. Later, Bilò et
al.[BCC+23] designed a $(3+\epsilon)$-approximate distance oracle in sub-
quadratic space and sublinear query time.

##  2 Preliminaries

We are given an undirected weighted graph $G$ where the weight of an edge is
integral and is in the range $[1\dots W]$. For an edge $e$, $w(e)$ denotes the
weight of $e$. The notation $st$ represents the shortest path from vertex $s$
to vertex $t$, and $|st|$ denotes its weight. For an edge $e=(u,v)$, $|se|$ is
defined as the minimum of $|su|$ and $|sv|$. Let $P$ be an arbitrary path from
$s$ to $t$. We write $P[s,t]$ to indicate that the path starts from $s$ and
ends at $t$. $P[t,s]$ is defined symmetrically. When considering an arbitrary
path $P$, in which vertex $u$ appears before vertex $v$, $P[u,v]$ refers to
the subpath from $u$ to $v$, and $|P[u,v]|$ represents its weight. Given two
paths $P[u,v]$ and $Q[v,w]$, $P\odot Q$ is the concatenation of $P$ with $Q$.
The notation $st\diamond F$ denotes the shortest path from $s$ to $t$,
avoiding a set of edges $F$, and $|st\diamond F|$ corresponds to its weight.
For an edge $e=(u,v)$, $se\diamond F:=\arg\min\\{|su\diamond F|,|sv\diamond
F|\\}$ and $es\diamond F:=\arg\min\\{|us\diamond F|,|vs\diamond F|\\}$. $V(F)$
denotes the set of vertices with endpoints in $F$. For any path $P$,
$(P)_{2}:=2^{\lfloor\log|P|\rfloor}$.

We will assume that the shortest path between any two vertices in the graph is
unique, even under edge failures. Uniqueness can be achieved by adding
suitable small weights to each edge (e.g., see [PP13]) – we can perturb the
edge weights such that any two paths between a pair of vertices have different
weights. This approach has also been used in [BK09b, HS01, GS18, DR22].

For any vertex $s$, $T_{s}$ denotes the shortest path tree from $s$.
$T_{s}(x)$ represents the subtree rooted at node $x$ in $T_{s}$. For each $s$,
we will store $T_{s}$. This takes $O(n^{2})$ space for all the vertices in the
graph. After constructing $T_{s}$, we can preprocess it such that it takes
$O(1)$ time to find the shortest path from $s$ to any other vertex in the
graph.

For each $0\leq i\leq\log(nW)$, we will find the first vertex on the $st$ path
that is at a distance $\geq 2^{i}$ from $s$. We can pre-process $T_{s}$ to
store this information for every $t\in G$. This additional data structure
takes $O(n^{2}\log(nW))$ space over all shortest path trees. Thus, we will
assume that we can find the first vertex that is at a distance $\geq 2^{i}$ on
the $st$ path in $O(1)$ time.

We can extend the above approach to find the $2^{i}$-th vertex not only on a
single path but on a collection of shortest paths. To this end, we define the
following:

######  Definition 2.1.

A path is termed $f$-decomposable if it is a concatenation of at most $f$
shortest paths interleaved with at most $f-1$ edges.

The shortest path in the graph is 1-decomposable. If a path $P$ is
$f$-decomposable, then it can be represented as $L_{1}\odot e_{1}\odot
L_{2}\odot e_{2}\odot\dots\odot e_{k-1}\odot L_{k}$ where each $L_{i}$ is a
shortest path and $k\leq f$. Also, the interleaving edges may or may not
exist. Thus, each $e_{i}$ is either an edge or may be empty. It takes only
$O(f)$ space to represent $P$ in the above form, making it easy to process. In
our algorithms, we will always output paths in the above form. Let us define
one more term to formalise this notion:

######  Definition 2.2.

If a path $P$ is represented as $L_{1}\odot e_{1}\odot L_{2}\odot
e_{2}\odot\dots\odot e_{k-1}\odot L_{k}$, where each $L_{i}$ (where $1\leq
i\leq k$) is a shortest path, each $e_{i}$ is either empty or is an edge and
$f\geq k$, then we say that $P$ is in an $f$-decomposable form.

If $P$ is in $f$-decomposable form, it becomes easy to process it, as can be
seen from the next lemma:

######  Lemma 2.3.

Let $P[s,t]$ be a path in $f$-decomposable form. Then, the first vertex at a
distance $\geq 2^{i}$ from $s$ on $P$ can be found in $O(f+\log(nW))$ time,
where $0\leq i\leq\log nW$.

This is an easy algorithmic problem, and we prove it in the appendix.

##  3 Overview

We begin with a fundamental result in this field.

######  Theorem 3.1.

([ABK+02, Theorem 2]) Let $G$ be an undirected weighted graph. For any $F\in
E^{f}$, $st\diamond F$ is $(f+1)$-decomposable.

Consequently, $st\diamond F$ contains at most $f+1$ segments, each of which is
a shortest path.

######  Definition 3.2.

(Intermediate vertex) A vertex $x\in st\diamond F$ is called an intermediate
vertex if it does not lie on the first and last segment of $st\diamond F$.

A straightforward strategy for finding $st\diamond F$ is to first locate an
intermediate vertex $x$ on it and then recursively search for $sx\diamond F$
and $xt\diamond F$. Both $sx\diamond F$, $xt\diamond F$ are $f$-decomposable,
reducing the problem to a smaller subproblem. The key challenge is finding an
intermediate vertex. But how to find $x$ if you don’t even know $st\diamond
F$? To solve this, we will try to find a “hitting set” $H$ that will satisfy
two properties:

  1. (I)

The size of $H$ is polynomial in $f$.

  2. (II)

There exists a vertex in $H$ that lies on $st\diamond F$ and serves as an
intermediate vertex.

There is a simple hitting set that satisfies (I) but only partially satisfies
(II). Consider a set of edges $F^{*}$ of size $f$ whose removal maximises the
distance between $s$ and $t$. We can show that either (i) $st\diamond\
F^{*}=st\diamond F$ or (ii) an edge of $F^{*}$ lies on the path $st\diamond
F$. In case (i), the answer is essentially the same as the output of the
maximiser. However, in case (ii), we find a small set $V(F^{*})$ of size
$O(f)$ that intersects $st\diamond F$. Unfortunately, this set may include
vertices from the first or last segments of $st\diamond F$, making this
maximiser less useful.

In [DR22], Ren and Duan developed an algorithm that uses different maximisers.
Using these maximisers, they identify a “hitting set” $H$ of size $O(f^{3})$
containing an intermediate vertex. Although we won’t delve into their approach
in detail, their maximiser has size $O(n^{4})$, and it is not clear how to
reduce this space.

###  3.1 A new approach

In this section, we describe our approach for handling a single fault in an
unweighted graph. Let $R=st\diamond e$, where $e=(u,v)$. We assume vertex $u$
is closer to $s$ along the $st$ path. The path $R$ deviates from the $st$ path
at $p$ and merges back at $q$ (refer to Figure 1). The detour of $R$ is the
path between $p$ and $q$ on $R$, or $R[p,q]$.

$st$ path$st\diamond e$$s$$p$$q$$t$$u$$v$$e$$x$$y$ Figure 1: $X$ is the set of
green vertices and $Y$ is the set of blue vertices. $x$ satisfies (a) and $y$
satisfies (b).

We ask the following question: can we find vertices $x,y\in R$ such that

  1. (a)

If $u$ is the nearest vertex of $V(F)$ from $x$, then $|xp|<(xu)_{2}$, and

  2. (b)

If $v$ is the nearest vertex of $V(F)$ from $y$, then $|yq|<(yv)_{2}$

Intuitively, $x$ is closer to $p$ than the nearest faulty edge. Similarly, $y$
is closer to $q$ than the nearest faulty edge. We will see later that we can
design maximisers using $x$ and $y$, such that the output of the maximiser not
only hits $R$ but also the detour of $R$. This increases our chances of
finding an intermediate vertex. However, the challenge is finding $x$ and $y$
when we don’t know $R$, $p$, and $q$.

For one fault, we will construct a small set $X$ and $Y$ that contains $x$ and
$y$, respectively. Let $X=\\{x_{1}=s,x_{2},\dots,x_{k}=u\\}$ be vertices on
$st$ path, where the distance between $x_{i-1}$ and $x_{i}$ is
$(x_{i-1}u)_{2}$. For instance, if $|su|=2^{\ell}-1$, $x_{1}=s$, $x_{2}$ is at
a distance $2^{\ell-1}$ from $x_{1}$, $x_{3}$ is at a distance $2^{\ell-2}$
from $x_{2}$ and so on. Similarly, we create sequence
$Y=\\{y_{1}=t,y_{2},\dots\\}$ on the $ts$ path, with distances between
$y_{i-1}$ and $y_{i}$ equal to $(y_{i-1}v)_{2}$. Both sequences are of length
$O(\log n)$.

Consider a vertex $x\in X$ just before $p$ on the $st$ path. If
$|xp|\geq(xu)_{2}$, then there exists another vertex of $X$ between $x$ and
$p$ on $st$ path, a contradiction. So $|xp|<(xu)_{2}$ and we satisfy (a).
Similarly, let $y\in Y$ be the vertex just before $q$ on the $ts$ path. Again,
$|yq|<(yv)_{2}$. Also, $R$ passes through both $x$ and $y$. Thus, we satisfy
(a) and (b) and $R=sx\odot xy\diamond e\odot yt$. In Section 6, we demonstrate
that it’s straightforward to find $xy\diamond e$ using the following
maximiser:

$\displaystyle\mathbb{D}(x,y,d_{1}=(xu)_{2},d_{2}=(yv)_{2})=\arg\max_{e^{*}\in
E}\Biggl{\\{}$ $\displaystyle|xy\diamond e^{*}|\leavevmode\nobreak\ \text{such
that}\ |xe^{*}|\geq d_{1}\text{ and }|ye^{*}|\geq d_{2}\Biggl{\\}}$

As we don’t know $x$ and $y$ in advance, we try all possible pairs in $X\times
Y$. Consequently, the time complexity of our algorithm is $O(\log^{2}n)$.
Also, the size of our maximiser is $O(n^{2}\log^{2}n)$.

Now, let’s generalise this approach to handle two faults. Suppose
$R=st\diamond\\{e_{1},e_{2}\\}$, with $e_{1}\in st$ and $e_{2}\in st\diamond
e_{1}$. Let $p$ be the vertex on $R$ from $s$, after which $R$ deviates from
$st\cup st\diamond e$. Symmetrically, define $q$. Let us assume that $p$ lies
on the path $st\diamond e_{1}$ and q lies on $st$ (See Figure 2). Consider a
sequence $X=\\{x_{1}=s,x_{2},\dots\\}$ on the $st\diamond e_{1}$ path, where
distance between any $x_{i-1}$ and $x_{i}$ is $\min_{u\in
V(F)}\\{(x_{i-1}u)_{2}\\}$. Similarly, we find a sequence $Y$ on $ts$ path.
Interestingly, even for two faults, we show that the size of $X$ and $Y$
remains $O(\log n)$, which is a significant generalisation detailed in Section
5.

$s$$p$$q$$t$$e_{1}$$e_{2}$$x$$y$$st$ path$st\diamond
e_{1}$$st\diamond\\{e_{1},e_{2}\\}$ Figure 2: $X$ is the set of green vertices
and $Y$ is the set of blue vertices. $x$ satisfies (a) and $y$ satisfies (b).

As before, there exists vertices $x\in X$ and $y\in Y$ satisfying (a) and (b)
respectively. Also, $R=sx\odot xy\diamond F\odot yt$. We will demonstrate how
to find $xy\diamond F$ by appropriately utilising multiple maximisers.
However, when multiple faults are present, finding $xy\diamond F$ is a bit
more involved and leverages ideas from [DR22]. Specifically, in Section 8, we
will show that we can identify a hitting set of size $O(f^{3})$ that contains
an intermediate vertex of $xy\diamond F$. This completes the overview.

##  4 Organisation of the paper

In Section 5, we introduce a new tool “Jump Sequence” which formalises the new
approach taken in this paper. In Section 6, as a warm-up, we apply our new
approach to design a single fault tolerant distance oracle in undirected
weighted graph. In Section 7 and Section 8, we extend our results to
$f$-faults.

##  5 A new tool: Jump Sequence

Let $R=st\diamond F^{\prime}$ where $F^{\prime}\subseteq F$ and $F$ is a set
of edges of size $f$. Let $u$ be a vertex in $V(F)$. Consider the sequence of
vertices $x_{1}=s,x_{2},x_{3},\ldots,x_{k}$ where, for $1\leq i\leq k-1$,
$x_{i}$ is the first vertex on path $R$ from $x_{i-1}$ satisfying

$|R[x_{i-1},x_{i}]|\geq\max\\{1,(x_{i-1}u\diamond F)_{2}\\}$ (1)

Imagine sitting at $x_{i-1}$ attached to a rope which starts at $u$. The
rope’s length is $(x_{i-1}u\diamond F)_{2}$, representing how far we can jump
on path $R$. The action of moving from $x_{i-1}$ to $x_{i}$ is called a _jump
from $x_{i-1}$ using $u$_. Observe that $x_{i}$ is at a distance at least
$(x_{i-1}u\diamond F)_{2}$ from $x_{i-1}$ along $R$. If $x_{i-1}u\diamond
F=0$, then we move to the vertex adjacent to $x_{i-1}$ on $R$.

$(x_{i-1}u\diamond F)_{2}$$s$$x_{i-1}$$x_{i}$$t$$u$ Figure 3: A jump from
$x_{i-1}$ using $u$.

Note that we can start the sequence from either $s$ or $t$, yielding different
sequences. We denote $\textsc{Jump}(R[s,t])$ as the sequence starting from $s$
and $\textsc{Jump}(R[t,s])$ as the other sequence. In this section, we focus
on $\textsc{Jump}(R[s,t])$, and all our results apply to $R[t,s]$ by symmetry.

In $\textsc{Jump}(R[s,t])$, we advance along $R[s,t]$ in steps of
$(x_{1}u\diamond F)_{2}$, $(x_{2}u\diamond F)_{2}$, and so on. Note that if
$u$ is on the path $R$, we simply transition from $u$ to its adjacent vertex
on $R$. For a clearer presentation in the subsequent section, we’ll assume $u$
is not on $R$, although our arguments remain valid even if $u$ is on $R$.

Consider the sequence $\\{(x_{1}u\diamond F)_{2},(x_{2}u\diamond
F)_{2},\dots,(x_{k-1}u\diamond F)_{2}\\}$. We claim that this sequence roughly
behaves like a bitonic sequence. That is, we can divide it at a vertex, say
$x_{j}$, such that:

  1. (A1)

In the sequence $\\{(x_{1}u\diamond F)_{2},(x_{2}u\diamond
F)_{2},\dots,(x_{j}u\diamond F)_{2}\\}$, the numbers decrease by at least a
factor of two after at most four jumps. Here, the jump from $x_{1}$ to $x_{2}$
in $\textsc{Jump}(R[s,t])$ implies jumping from $(x_{1}u\diamond F)_{2}$ to
$(x_{2}u\diamond F)_{2}$ in the above sequence.

  2. (A2)

In the sequence $\\{(x_{j}u\diamond F)_{2},(x_{j+1}u\diamond
F)_{2},\dots,(x_{k}u\diamond F)_{2}\\}$, the numbers increase by a factor of
two after every four jumps.

The above assertion implies the following lemma:

######  Lemma 5.1.

The length of $\textsc{Jump}(R[s,t])$ is $\leq 8\log(nW)$

We now prove (A1). Let $(x_{1}u\diamond F)_{2}=2^{\ell}$ (for some $\ell\geq
0$). Consider the next four vertices after $x_{1}$. If, for any
$i\in\\{2,3,4,5\\}$, $(x_{i}u\diamond F)_{2}\leq 2^{\ell-1}$, then after at
most 4 jumps, we find a vertex $x_{i}$ where $(x_{i}u\diamond F)_{2}$
decreases by atleast half. We repeat this process until we reach a vertex, say
$x_{j}$, for which this condition no longer holds. This proves (A1).

Now, let’s prove (A2). Assume $(x_{j}u\diamond F)_{2}=2^{\ell}$. By
construction, for all $i\in\\{j+1,j+2,j+3,j+4\\}$, $(x_{i}u\diamond F)_{2}\geq
2^{\ell}$. To prove (A2), we first need to demonstrate that $(x_{j+4}u\diamond
F)_{2}\geq 2^{\ell+1}$. To do so, we establish the following stronger
statement:

######  Lemma 5.2.

Let $(x_{j}u\diamond F)_{2}=2^{\ell}$ and for all
$i\in\\{j+1,j+2,j+3,j+4\\},(x_{i}u\diamond F)_{2}\geq 2^{\ell}$. Then, for all
$i\geq j+4p$, $(x_{i}u\diamond F)_{2}\geq 2^{\ell+p}$ where $p\geq 1$.

###### Proof.

We prove this lemma by induction on $p$.

Base Case ($p=1$): For $i\geq j+4$, assume for contradiction that
$(x_{i}u\diamond F)_{2}\leq 2^{\ell}$. By construction, $R[x_{j},x_{i}]\geq
4\times 2^{\ell}$ because $x_{j},x_{j+1},x_{j+2},x_{j+3},x_{j+4}$ are
consecutively at a distance $\geq 2^{\ell}$ on $R[s,t]$. However, there is an
alternate path from $x_{j}$ to $x_{i}$ avoiding $F$, which is $x_{j}u\diamond
F\odot x_{i}u\diamond F$. The sum of their weights is
$<2^{\ell+1}+2^{\ell+1}=4\times 2^{\ell}$, contradicting the fact that
$R[x_{j},x_{i}]$ is the shortest path from $x_{j}$ to $x_{i}$ avoiding
$F^{\prime}\subseteq F$.

Inductive Step ($p>1$): Assume that for all $i\geq j+4(p-1)$, $(x_{i}u\diamond
F)_{2}\geq 2^{\ell+p-1}$. We will now show that for any $i\geq j+4p$,
$(x_{i}u\diamond F)_{2}\geq 2^{\ell+p}$. For contradiction, assume that
$(x_{i}u\diamond F)_{2}\leq 2^{\ell+p-1}$.

Consider the path $R[x_{j},x_{i}]$. As in the base case, the subpath
$R[x_{j},x_{j+4}]$ of $R[x_{j},x_{i}]$ has weight $\geq 4\times 2^{\ell}$.
Similarly, using the induction hypothesis, the weight of the path from the
vertex $x_{j+4(p-1)}$ to $x_{j+4p}$ is $\geq 4\times 2^{\ell+p-1}$. Thus, the
weight of the path $R[x_{j},x_{i}]$ is $\geq 4\times 2^{\ell}+4\times
2^{\ell+p-1}>2^{\ell+1}+\ 2^{\ell+p}$. However, there is an alternate path
from $x_{j}$ to $x_{i}$ that avoids $F$. This path is $x_{j}u\diamond F\odot
x_{i}u\diamond F$. The sum of the weights of these two paths is
$<2^{\ell+1}+2^{\ell+p}$. This is a contradiction as $R[x_{j},x_{i}]$ is the
shortest path from $x_{j}$ to $x_{i}$ avoiding $F^{\prime}\subseteq F$. This
completes the proof of the lemma. ∎

We now extend our result to all vertices in $V(F)$.

###  5.1 Jump Sequence using the fault set $F$

Let’s create another jump sequence $\textsc{Jump}(R[s,t])$ that utilizes each
vertex of $V(F)$. The first vertex in $\textsc{Jump}(R[s,t])$ is $x_{1}:=s$.
The $i$-th vertex in $\textsc{Jump}(R[s,t])$ is defined as follows: we first
find the vertex $u=\text{argmin}_{v\in V(F)}\\{(x_{i-1}v)_{2}\\}$. Then, we
jump from $x_{i-1}$ using $u$ on the path $R$. In other words, $x_{i}$ is the
first vertex after $x_{i-1}$ on the path $R$ that satisfies:

$|R[x_{i-1},x_{i}]|\geq\max\\{1,(x_{i-1}u\diamond F)_{2}\\}$ (2)

Notice that by definition, $x_{i-1}u\diamond F=x_{i-1}u$. This is because $u$
is the closest vertex of $V(F)$ to $x_{i-1}$. Therefore, instead of writing
$x_{i-1}u\diamond F$ (as in the previous section), we simply write $x_{i-1}u$.
Assuming the setting in above paragraph, we claim the following lemma:

######  Lemma 5.3.

The length of $\textsc{Jump}(R[s,t])$ is $\leq 16f\log(nW)$.

###### Proof.

Let $u\in V(F)$. Let $\\{y_{1},y_{2},\dots,y_{\ell}\\}$ be the subsequence of
$\textsc{Jump}(R[s,t])$ where we jump using $u$. Consider the sequence
$\\{(y_{1}u)_{2},(y_{2}u)_{2},\dots,(y_{\ell-1}u)_{2}\\}$. We claim that this
sequence also behaves like a bitonic sequence satisfying (A1) and (A2). The
proof remains exactly the same as in the previous section. Thus, the length of
this subsequence is $\leq 8\log(nW)$. Since there are at most $2f$ vertices in
$V(F)$, the length of $\textsc{Jump}(R[s,t])$ is $\leq 16f\log(nW)$. ∎

##  6 Single fault tolerant distance oracle

In our new single fault tolerant distance oracle, we will crucially use the
jump sequence with a suitable maximiser. Before describing our maximiser, we
note its crucial property :

######  Lemma 6.1.

([DR22, Claim 4.2]) Let $\mathbb{D}$ be a maximiser returning an edge set
$F^{*}$ maximising $|st\diamond F^{*}|$. If $F$ satisfies the maximiser’s
condition, then either (1) $st\diamond F=st\diamond F^{*}$ or (2) an edge in
$F^{*}$ lies on the path $st\diamond F$.

###### Proof.

Let us assume that no edge of $F^{*}$ lies on the path $st\diamond F$. So,
$st\diamond F$ avoids $F^{*}$ also. Hence, $\underbrace{\text{$|st\diamond
F|\geq|st\diamond F^{*}|$}}_{\text{($\alpha$)}}$ as $st\diamond F^{*}$ is the
shortest path avoiding $F^{*}$.

Now, if $F$ satisfies the maximiser’s conditions and $F^{*}$ is the output of
the maximiser, then $\underbrace{\text{$|st\diamond F^{*}|\geq|st\diamond
F|$}}_{\text{($\beta$)}}$. $(\alpha)$ and $(\beta)$ implies $|st\diamond
F|=|st\diamond F^{*}|$. Also, since we preprocessed the graph ensuring unique
shortest path, $st\diamond F=st\diamond F^{*}$. This completes the proof. ∎

For all our maximisers, $F$ will satisfy its condition. Case (1) in Lemma 6.1
is good for us, as it allows us to return $st\diamond F^{*}$. In most parts of
this paper, we focus on case (2). Now, let’s examine the maximiser for our
single fault-tolerant distance oracle.

###  6.1 Maximiser

$\displaystyle\mathbb{D}(x,y,d_{1},d_{2})=\arg\max_{e^{*}\in E}\Biggl{\\{}$
$\displaystyle|xy\diamond e^{*}|\leavevmode\nobreak\ \text{such that
$|xe^{*}|\geq d_{1}$ and $|ye^{*}|\geq d_{2}$ }$ $\displaystyle\text{where
both $d_{1}$ and $d_{2}$ are a power of 2.}\Biggl{\\}}$ (3)

In addition to returning $e^{*}$, our maximiser will also return $xy\diamond
e^{*}$. In our algorithm, we will write $(e^{*},xy\diamond
e^{*})\leftarrow\mathbb{D}(x,y,d_{1},d_{2})$ to indicate this fact. By Theorem
3.1, $xy\diamond e^{*}$ is $2$-decomposable and we can represent it in
2-decomposable form. Thus, the space required to store $(e^{*},xy\diamond
e^{*})$ is $O(1)$. For a fixed pair $x,y$, there are $O(\log(nW))$ possible
values of $d_{1}$ and $d_{2}$. Thus, there are $O(\log^{2}(nW))$ possible
maximisers each taking $O(1)$ space. We construct maximisers for all pair of
vertices in the graph. Thus, the size of our data-structure is
$O(n^{2}\log^{2}(nW))$.

###  6.2 Query Algorithm

Let us now describe our algorithm $\textsc{Query}(s,t,e=(u,v))$ (See Algorithm
1). Let us assume that $e$ lies on the $st$ path such that $u$ is closer to
$s$ than $v$. We first find $\textsc{Jump}(st)$ and $\textsc{Jump}(ts)$ using
$e$. This is done by calling the function $\textsc{FindJump}()$.

We store our final answer in Path, which is initialised to $\emptyset$. We
define $|\textsc{Path}|=\infty$, if $\textsc{Path}=\emptyset$. For each pair
$(x,y)$ in $\textsc{Jump}(st)$ and $\textsc{Jump}(ts)$, we call the maximiser
$\mathbb{D}(x,y,(xu)_{2},(yv)_{2})$. Note that by construction, $e$ satisfies
the condition of the maximiser. The maximiser returns $(e^{*},xy\diamond
e^{*})$. Then, we set $P=sx\odot xy\diamond e^{*}\odot yt$. We then check if
$P$ contains $e$ or not. If $P$ does not contain $e$, then we update our Path.
This completes the description of our algorithm.

1 $\textsc{Jump}(st)\leftarrow\textsc{FindJump}(st,\\{e\\})$;

2 $\textsc{Jump}(ts)\leftarrow\textsc{FindJump}(ts,\\{e\\})$;

3 $\textsc{Path}\leftarrow\emptyset$;

4 foreach  _$(x,y)\in\textsc{Jump}(st)\times\textsc{Jump}(ts)$_ do

5 $(e^{*},xy\diamond e^{*})=\mathbb{D}(x,y,(xu)_{2},(yv)_{2})$ ;

6 $P\leftarrow sx\odot xy\diamond e^{*}\odot yt$

7 if  _$e\notin P$_ then

8 $\textsc{Path}\leftarrow\text{argmin}\\{|P|,|\textsc{Path}|\\}$;

9

10

11return Path;

Algorithm 1 $\textsc{Query}(s,t,e=(u,v))$: returns $st\diamond\ e$

1 $X\leftarrow\emptyset$;

2 $x\leftarrow s$;

3

4do

5 $X\leftarrow X\cup\\{x\\}$;

6 $u=\arg\min_{v\in V(F)}\\{(xv)_{2}\\}$;

7 Let $y$ be the first vertex on $P[x,t]$ path at distance
$\geq\max\\{1,(xu)_{2}\\}$from $x$;

8 if  _$y$ exists_ then

9 $x\leftarrow y$;

10

11

12while  _ $y$ exists_;

return $X$

Algorithm 2 FindJump($P[s,t],F)$

####  6.2.1 Correctness

In our algorithm, we always update Path with $P$ that does not contain $e$.
Thus, $|\textsc{Path}|\geq|st\diamond e|$. We will now show that there is a
pair, say $(x,y)\in\textsc{Jump}(st)\times\textsc{Jump}(ts)$ for which both
$P$ and Path will be set to $st\diamond e$. This will imply that our algorithm
is correct.

Let $R=st\diamond e$. Let us also assume that the detour of $R$ starts at the
vertex $p$ on the $su$ path and ends at the vertex $q$ on the $vt$ path (See
Figure 1). Consider the jump sequence $\textsc{Jump}(st)$. Let $x$ be the last
vertex before $p$ on $\textsc{Jump}(st)$ on the $st$ path. Thus, we have,
$xp<(xu)_{2}$. Since the detour of $R$ starts at the vertex $p$, $R[x,p]=xp$.
Thus, we have:

$|R[x,p]|<(xu)_{2}$ (4)

Similarly, in the jump sequence $\textsc{Jump}(ts)$, let $y$ be the last
vertex such that $ty\leq tq$. Consider the maximiser on the pair $(x,y)$:
$\mathbb{D}(x,y,(xu)_{2},(yv)_{2})$. Let $e^{*}$ be the edge returned by this
maximiser. Note that $e^{*}$ must lie on the $xy$ path, as the weight of any
other path from $x$ to $y$ is strictly greater than the weight of the $xy$
path. Thus, we have:

$e^{*}$ lies on the shortest $xy$ path which is a subpath of $st$ (5)

There are two cases:

  1. 1.

$e^{*}$ does not lie on the path $xy\diamond e$.

Since $e$ also satisfies the conditions of the maximiser, by Lemma 6.1,
$xy\diamond e^{*}=xy\diamond e$. Thus, we correctly set $P$ to:

$P=sx\odot xy\diamond e^{*}\odot yt=sx\odot xy\diamond e\odot yt=R$

Now, we show that we can represent $P$ in 2-decomposable form in our
algorithm. By construction, $xy\diamond e^{*}$ is in 2-decomposable form, say
$L_{1}\odot e^{\prime}\odot L_{2}$. But even $R$ is 2-decomposable and
$xy\diamond e^{*}$ is a subpath of $R$. Thus, $sx\odot L_{1}$ must be a
shortest path. Similarly, $L_{2}\odot yt$ is also a shortest path. Thus, the
path $P$ is in $2$-decomposable form.

  2. 2.

$e^{*}$ lies on the path $xy\diamond e$ or $R[x,y]$

We will see this case cannot arise. By the condition of the maximiser,
$|xe^{*}|\geq(xu)_{2}$ or $R[x,e^{*}]\geq(xu)_{2}$. Using the previous
inequality and Equation 4, $e^{*}$ lies after $p$ on $R$. But the detour of
$R$ starts at $p$. Thus, $e^{*}$ cannot lie on $xu$ path. Similarly, we can
show that $e^{*}$ does not lie on $yv$. This implies that $e^{*}$ does not lie
on $xy$ path. But this violates Equation 5. So this case cannot arise.

####  6.2.2 Running Time

Let us first find the time taken by $\textsc{FindPath}(st)$. By Lemma 5.3,
there are $O(\log(nW))$ vertices in $\textsc{Jump}(st)$. Thus, in
$\textsc{FindPath}(st)$, the while loop runs for $O(\log((nW))$ time. In the
while loop, in Algorithm 2, we find a vertex which is at a distance $2^{i}$
(for some $i$) on some shortest path. This can be done in $O(1)$ time. Apart
from this, all other operations in the while loop can also be performed in
$O(1)$ time. Thus, the running time of $\textsc{FindPath}(st)$ (and similarly
$\textsc{FindPath}(ts)$) is $O(\log(nW))$.

Next, we process every pair of vertices in $\textsc{Jump}(st)$ and
$\textsc{Jump}(ts)$. We will show that the time taken to process each pair is
$O(1)$ implying that the running time of our query algorithm is
$(\log^{2}(nW))$.

While processing a pair in $\textsc{Jump}(st)\times\textsc{Jump}(ts)$, the
dominating step is to check if $P$ contains $e$ (in Algorithm 1). To check if
a shortest path, say $ab,$ contains $e$, we can check if
$|ae|+w(e)+|eb|=|ab|$. Since $P$ is in 2-decomposable form, we can check if
$P$ contains $e$ or not in $O(1)$ time.

Thus, we have proven the following:

######  Lemma 6.2.

There is a single fault tolerant distance oracle that takes
$O(n^{2}\log^{2}(nW))$ space and answers each query in $O(\log^{2}(nW))$ time.
Moreover, it returns a path in 2-decomposable form.

##  7 From single fault to $f$ faults

In the single-fault algorithm, we know that the fault $e$ must lie on the $st$
path. Also, the detour of $st\diamond e$ starts and ends on the $st$ path. But
what happens with multiple faults? How do we define the start and end of the
detour? To address this, we introduce some new notations.

We label the shortest path from $s$ to $t$ as path $P_{1}$. Let $e_{1}\in F$
be an edge on $P_{1}$. Then, $st\diamond e_{1}$ is referred to as path
$P_{2}$. Let us assume that $e_{2}\in F$ is an edge on $P_{2}$. Then $P_{3}$
is $st\diamond\\{e_{1},e_{2}\\}$. We now generalise this recursive definition.

######  Definition 7.1.

(Path $P_{i}$’s)

For the base case, let $P_{1}=st$. Let $e_{1},e_{2},\dots,e_{i-1}$ be the
distinct edges of $F$ on paths $P_{1},P_{2},\dots,P_{i-1}$ respectively where
$1\leq i\leq f$. Then, $P_{i}$ is $st\diamond\\{e_{1},e_{2},\dots,e_{i-1}\\}$.

For notational convenience, we define $P_{0}=\emptyset$. We will now define
the notion of the detour of a path, its start and end.

######  Definition 7.2.

(Prefix and suffix of $P_{i}$) Let $e$ be the first faulty edge on $P_{i}$
from $s$. Then $\textsc{Prefix}(P_{i})=P_{i}[s,e]$. Similarly, if $e$ is the
first faulty edge on $P_{i}$ from $t$, then
$\textsc{Suffix}(P_{i})=P_{i}[t,e]$.

######  Definition 7.3.

(Detour of $st\diamond F$, its start and end)

Let $p_{out}$ be the first vertex in $st\diamond F$ from $s$ that does not lie
in $\cup_{j=1}^{f}\textsc{Prefix}(P_{j})$ and $p$ be the vertex before
$p_{out}$ in $st\diamond F$. If $p$ is in $\textsc{Prefix}(P_{i})$ but not in
$\textsc{Prefix}(P_{0})\cup\textsc{Prefix}(P_{1})\cup\dots\cup\textsc{Prefix}(P_{i-1})$
(where $1\leq i\leq f$), then the detour of $st\diamond F$ starts on path
$P_{i}$ at $p$. We define the end of a detour symmetrically (using Suffix
instead of Prefix). Let $q$ be the vertex where the detour of $st\diamond F$
ends. The path between $p$ and $q$ on $st\diamond F$ is called the detour of
$st\diamond F$.

For example, in Figure 2, the detour of $st\diamond F$ starts on the path
$P_{2}$ at $p$ as $p\in\textsc{Prefix}(P_{2})$ but not in
$\textsc{Prefix}(P_{0})\cup\textsc{Prefix}(P_{1})$. Similarly, the detour of
$st\diamond F$ ends on $P_{1}$ at $q$ as $q\in\textsc{Suffix}(P_{1})$ but not
in $\textsc{Suffix}(P_{0})$.

Assume wlog that the detour of $st\diamond F$ starts on $p\in P_{i}$ and ends
on $q\in P_{j}$. Similar to the single fault tolerant distance oracle, we find
$\textsc{Jump}(P_{i}[s,t])$ and $\textsc{Jump}(P_{j}[t,s])$. In
$\textsc{Jump}(P_{i}[s,t])$, let $x$ be the last vertex before $p$ in
$P_{i}[s,t]$(see Figure 2). Similarly, let $y\in\textsc{Jump}(P_{j}[t,s])$ be
the last vertex before $q$ in $P_{j}[t,s]$. For the pair $(x,y)$, we use an
appropriate maximiser, $(F^{*},xy\diamond
F^{*})\leftarrow\mathbb{D}(x,y,\cdot,\cdot)$ to find $xy\diamond F$ (we will
define the maximiser later). In the single fault tolerant distance oracle, we
proved no edge in $F^{*}$ lies on $xy\diamond F$. Unfortunately, here, a
vertex in $V(F^{*})$ may lie on $xy\diamond F$. Let’s consider the easier
case. If a vertex $u\in V(F^{*})$ is an intermediate vertex on $xy\diamond F$,
we can recurse on $su\diamond F$ and $ut\diamond F$. But, if $u$ lies on the
first or last segment of $xy\diamond F$, we follow [DR22]. In this case, we
will see that $u$ will be a "clean" vertex. We now define this notion.

######  Definition 7.4.

(Intact from failure $F$)

A path is intact from failure $F$ if no edge of $F$ lies on the path. A tree
$T$ is intact from failure $F$ if none of the vertices of $V(F)$ are in $T$.

######  Definition 7.5.

($x$-clean and $y$-clean from failure $F$)

Let $R=xy\diamond F$. A vertex $u\in R$ is called $x$-clean from failure $F$
if $xu$ and $T_{x}(u)$ is intact from failure $F$. We call $u$ an $x$-clean
vertex, dropping the term “from the failure $F$” where it is clear from the
context. Similarly, define a $y$-clean vertex.

An $x$-clean vertex $u$ lies on the first segment of $R$, as $x\in R$ and $xu$
is intact from failure $F$. Additionally, $T_{x}(u)$ is also intact from
failure $F$. As in [DR22], once we find an $x$-clean vertex $u$, we can build
a suitable maximiser that finds a fault set $F^{\prime}$ that:

maximises $|xy\diamond F^{\prime}|$ such that $u$ is $x$-clean from failure
$F^{\prime}$.

Assume that a vertex $v\in V(F^{\prime})$ lies on $xy\diamond F$. We will
later show that $v$ cannot lie on the first segment of $xy\diamond F$, which
fixes the problem for the first segment. Similarly, we can address the issue
for the last segment by finding a $y$-clean vertex. Assuming we have found
both an $x$-clean vertex $u$ and a $y$-clean vertex $v$, we can construct a
suitable maximiser that finds a fault set $F^{\prime\prime}$ that:

maximises $st\diamond F^{\prime\prime}$, ensuring that $u$ is $x$-clean from
failure $F^{\prime\prime}$ and $v$ is $y$-clean from failure
$F^{\prime\prime}$.

We will show that a vertex in $V(F^{\prime\prime})$ cannot lie on the first or
last segments of $xy\diamond F$; if it lies on $xy\diamond F$, it must be an
intermediate vertex. Though we are following an approach similar to [DR22],
the space required for all our maximisers (which are different from their
maximisers) will be $O(f^{4}n^{2}\log^{2}(nW))$. This completes the overview
of our algorithm.

##  8 $f$\- fault Tolerant Distance Oracle

In this section, we will prove Theorem 1.1 using induction on $f$. For the
base case, i.e., $f=1$, we can use the single fault tolerant distance oracle
in Section 6. Let us assume using the induction hypothesis that we have a
fault tolerant distance oracle for $1,2,\dots,f-1$ faults. In the rest of the
paper, we design an $f$-fault tolerant distance oracle. We will assume that we
want to find the shortest path from $s$ to $t$ avoiding $F$.

To find $st\diamond F$, we will call the function $\textsc{Query}(s,t,r=f+1)$.
For brevity, we drop the fault set $F$ from the arguments given to the query
algorithm. The first argument of Query is the source and the second argument
is the destination. The third argument $r$ suggests to us that the path
$st\diamond F$ is $r$-decomposable. Initially, we call Query with $r=f+1$. Let
us now describe the Query algorithm (See Algorithm 3).

By induction hypothesis, using 1-fault, 2-fault$,\dots,f-1$-fault tolerant
distance oracles, we find paths $P_{2},\dots,P_{f}$ respectively. This is done
in the function FindPath. In Section 10, we will prove:

######  Lemma 8.1.

FindPath returns paths $P_{1},P_{2},\dots,P_{f}$ in $\leq
10c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}}(nW)$ time.

For each path $P_{i}$, we then find $\textsc{Jump}(P_{i}[s,t])$ and
$\textsc{Jump}(P_{i}[t,s])$. Our query algorithm will return the answer stored
in the variable Path which is initialised to $\emptyset$.

1 if  _$r=0$_ then

2 return $\infty$;

3

4$P_{1},P_{2},\dots,P_{f}\leftarrow\textsc{FindPath}(s,t,F)$;

5

6foreach  _$i=1$ to $f$_ do

7 $\textsc{Jump}(P_{i}[s,t])\leftarrow\textsc{FindJump}(P_{i}[s,t],F)$;

8 $\textsc{Jump}(P_{i}[t,s])\leftarrow\textsc{FindJump}(P_{i}[t,s],F)$;

9

10$\textsc{Path}=\phi$;

11 for  _$(i,j)\in[1\dots f]\times[1\dots f]$_ do

12 $\textsc{Intermediate}\leftarrow\emptyset$;

13 foreach
_$(x,y)\in\textsc{Jump}(P_{i}[s,t])\times\textsc{Jump}(P_{j}[t,s])$_ do

// $x$ satisfies the condition of an intermediate vertex

14 if  _$sx$ and $xt$ contain an edge from $F$_ then

15 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup\\{x\\}$;

16

// $y$ satisfies the condition of an intermediate vertex

17 else if  _$sy$ and $yt$ contain an edge from $F$_ then

18 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup\\{y\\}$;

19

20 else

21 $(P,I)\leftarrow\textsc{Find-Intermediate}_{1}(x,y,r)$;

22

23 $P^{\prime}\leftarrow sx\odot P\odot yt$;

24

25 $\textsc{Path}=\text{argmin}\\{|\textsc{Path}|,|P^{\prime}|\\}$;

26

27 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup I$;

28

29

30 foreach  _$u\in\textsc{Intermediate}$_ do

31
$\textsc{Path}\leftarrow\text{argmin}\\{|\textsc{Query}(s,u,r-1)\odot\textsc{Query}(u,t,r-1)|,|\textsc{Path}|\\}$;

32

33

34return Path;

Algorithm 3 Query$(s,t,r)$

The detour of $st\diamond F$ may start and end on $P_{i}$ and $P_{j}$,
respectively. Since we do not know $i$ and $j$ beforehand, we will run our
algorithm for every possible $i,j$ pair. We consider each pair $(x,y)$ in
$\textsc{Jump}(P_{i}[s,t])\times\textsc{Jump}(P_{j}[t,s])$. If $x$ or $y$
satisfies the condition of an intermediate vertex, then we add it to the set
of Intermediate vertices. Otherwise, we call $\textsc{Find-
Intermediate}_{1}(x,y,r)$ which returns a tuple $(P,I)$. In the tuple, $P$ is
a path and $I$ is a candidate set of intermediate vertices. In Section 9, we
will show that $\textsc{Find-Intermediate}_{1}(x,y,r)$ finds an intermediate
vertex in $xy\diamond F$ if $(x,y)$ satisfies the following setting:

  1. (S1)

Let $st\diamond F$ be a $r$-decomposable path and the detour of $st\diamond F$
starts on $P_{i}$ at the vertex $p$ and ends on $P_{j}$ at the vertex $q$. Let
$x$ is the last vertex of $\textsc{Jump}(P_{i}[s,t])$ before $p$ on
$P_{i}[s,t]$. Similarly, $y$ is the last vertex of $\textsc{Jump}(P_{j}[t,s])$
before $q$ on $P_{j}[t,s]$. Also, $x$ and $y$ are not intermediate vertices on
$st\diamond F$ (See Figure 2 for an example).

######  Lemma 8.2.

Let $(P,I)\leftarrow\textsc{Find-Intermediate}_{1}(x,y,r)$. The function
$\textsc{Find-Intermediate}_{1}$ comes with the following guarantees: $P$ is a
path that avoids $F$, $I$ is a set of size $\leq 8f^{3}$ and the running time
of procedure $\textsc{Find-Intermediate}_{1}(x,y,r)$ is $O(f^{4})$.
Moreover, if $(x,y)$ satisfies (S1), then either

  1. 1.

$P=xy\diamond F$ or

  2. 2.

$I$ contains an intermediate vertex on the path $xy\diamond F$.

Moreover, $P$ is in $r$-decomposable form.

Some remarks are in order. The function $\textsc{Find-
Intermediate}_{1}(x,y,r)$ has no guarantees, except for running time, fault
free path $P$ and the size of set $I$, if $(x,y)$ does not satisfy (S1). If
$(x,y)$ satisfies (S1), then in the first case, we get $xy\diamond F$ itself.
Else, at least one vertex in $I$ is an intermediate vertex on $xy\diamond F$.

If $(x,y)$ satisfies (S1), an intermediate vertex in $xy\diamond F$ is also an
intermediate vertex in $st\diamond F$. Since we do not know the intermediate
vertex beforehand, we add all vertices of $I$ to Intermediate and recurse our
algorithm on each vertex in Intermediate. This completes the description of
our algorithm. We now show that our algorithm is correct.

###  8.1 Correctness

We will first show that our algorithm always returns a Path that avoids $F$.
In $\textsc{Query}(x,y,r)$, Path is set at Algorithm 3 and Algorithm 3. In
Algorithm 3, $sx$ and $yt$ are intact from failure $F$ as both $x$ and $y$ are
not intermediate vertices. Also, using Lemma 8.2, $P$ avoids $F$. Thus,
$P^{\prime}$ and in turn Path avoids $F$. Similarly, we can prove using
induction that the Path set in Algorithm 3 also avoids $F$. Thus,
$|\textsc{Path}|\geq|st\diamond F|$. We will now show that there is a pair
$(x,y)$ for which Path is set to $st\diamond F$ in our algorithm. To this end,
we prove the following lemma.

######  Lemma 8.3.

If $st\diamond F$ is $r$-decomposable, then $\textsc{Query}(s,t,r^{\prime})$
will return it in $r$-decomposable form where $r^{\prime}\geq r$.

###### Proof.

We prove this lemma using induction on $r$.

Base Case ($r=2$): Let us prove the base case when $r^{\prime}=2$. The proof
remains the same even if $r^{\prime}>2$.

  1. 1.

$\textsc{Query}(s,t,2)$ returns the correct path.

As $st\diamond F$ is $2$-decomposable, no pair $(x,y)$ processed by our
algorithm can be intermediate vertices. Let us assume that we process a pair
$(x,y)$ that satisfies (S1). In that case, we call
$(P,I)\leftarrow\textsc{Find-Intermediate}_{1}(x,y,2)$.

Since $st\diamond F$ is 2-decomposable, so is $xy\diamond F$. Thus, $I$ is
empty. By Lemma 8.2, $P=xy\diamond F$, and we have found the correct path,
that is, $sx\odot P\odot yt$.

  2. 2.

The path returned by $\textsc{Query}(s,t,2)$ is in $2$-decomposable form.

By Lemma 8.2, $P$ is in 2-decomposable form, say $L_{1}\odot e^{\prime}\odot
L_{2}$. But even $st\diamond F$ is 2-decomposable and $P$ is a subpath of
$st\diamond F$. Thus, $sx\odot L_{1}$ must be a shortest path. Similarly,
$L_{2}\odot yt$ is also a shortest path. Thus, the path $sx\odot P\odot yt$
can be represented in $2$-decomposable form.

Using the induction hypothesis, let us assume that Query returns the correct
answer for paths that are $f$ decomposable.

Inductive step ($r=f+1$): Again, let us prove the lemma when $r^{\prime}=f+1$.

  1. 1.

$\textsc{Query}(s,t,f+1)$ returns the correct path.

Let us assume that we process a pair $(x,y)$ in $\textsc{Query}(s,t,f+1)$. If
$x$ is an intermediate vertex, then we can recurse using
$\textsc{Query}(s,x,f)\odot\textsc{Query}(x,t,f)$. By induction hypothesis,
both these functions return the correct path, and we are done. Similarly, if
$y$ is an intermediate vertex, we are done. So, let us assume that neither $x$
nor $y$ is an intermediate vertex. Specifically, look at the pair $(x,y)$ that
satisfies (S1). In that case, we call $(P,I)\leftarrow\textsc{Find-
Intermediate}_{1}(x,y,f+1)$. If $P=xy\diamond F$, then we have found the
correct path, that is $sx\odot P\odot yt$.

Otherwise, using Lemma 8.2, there is an intermediate vertex, say $u\in I$ on
the path $xy\diamond F$. Since $xy\diamond F$ is a subpath of $st\diamond F$,
$u$ is an intermediate vertex even for $st\diamond F$. We then recurse using
$\textsc{Query}(s,u,f)\odot\textsc{Query}(u,t,f)$. By induction hypothesis,
both these functions return the correct path, and we are done.

  2. 2.

The path returned by $\textsc{Query}(s,t,f+1)$ is in $f+1$-decomposable form.

There are two places where we set Path. They are:

    1. (a)

Algorithm 3

In Algorithm 3, the algorithm sets Path to $sx\odot P\odot yt$. By Lemma 8.2,
$P$ is in $f+1$-decomposable form. Let the first and the last segment of $P$
be $xa$ and $by$ (for some vertex $a$ and $b$). But even $st\diamond F$ is
$f+1$-decomposable. Also, since $x$ and $y$ are not intermediate vertices, $x$
lies on the first segment of $st\diamond F$ and $y$ lies on its last segment.
Thus, $sx\odot xa$ is the first segment of $st\diamond F$. Similarly, $by\odot
yt$ is the last segment of $st\diamond F$. Thus, we also return a path in
$f+1$ decomposable form in Algorithm 3.

    2. (b)

Algorithm 3

Let $u$ be an intermediate vertex in $st\diamond F$. Since $st\diamond F$ is
$f+1$ decomposable, we can represent is as $st\diamond F=L_{1}\odot e_{1}\odot
L_{2}\odot e_{2}\odot\dots\odot e_{f}\odot L_{f+1}$ where each $L_{i}$ (where
$2\leq i\leq f$) is a shortest path and each $e_{i}$ is an interleaving edge.
Wlog, let us assume that $u$ is in $L_{i}$. By induction hypothesis,
$\textsc{Query}(s,u,f)$ will return a path in $i$ decomposable form as
$su\diamond F$ is an $i$-decomposable path. Similarly, $\textsc{Query}(u,t,f)$
will return the path $ut\diamond F$ in $(f-i+2)$ decomposable form. As the
last shortest path of $su\diamond F$ and the first shortest path of
$ut\diamond F$ has no interleaving edges, we can merge them and get a path in
$(f+1)$ decomposable form.

This completes our proof. ∎

###  8.2 Running Time

We now calculate the running time of $\textsc{Query}(s,t,r)$.

######  Lemma 8.4.

The running time of $\textsc{Query}(s,t,r)$ is $\leq
c^{f^{2}+r}f^{8(f^{2}+r)}\log^{2(f^{2}+r)}(nW)$ where $c>1$ is a constant.

If we put $r=f+1$ in the above equation, we get the running time of
$\textsc{Query}(s,t,f+1)$ to be $\leq
c^{(f+1)^{2}}f^{8(f+1)^{2}}\log^{2(f+1)^{2}}(nW)$ as required.

###### Proof.

We will prove using induction on $r$. Let $T(r)$ be the running time of
$\textsc{Query}(s,t,r)$. For the base case, $r=0$, $T(0)=1$. Using induction
hypothesis, let us assume that $T(1),T(2),\dots,T(r-1)$ satisfies the
statement of the lemma. We want to find $T(r)$. Let us first find the running
time of $\textsc{Query}(s,t,r)$ excluding recursive calls. In
$\textsc{Query}(s,t,r)$, we find the paths $P_{1},P_{2},\dots,P_{f}$ using
$\textsc{FindPath}()$. Using Lemma 8.1, $\textsc{FindPath}()$ takes
$\leq\underbrace{10c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}}(nW)}_{\alpha}$ time.

Then, we find the jump sequence for each path $P_{i}$. Using induction
hypothesis, the path $P_{i}$ is in $i$-decomposable form or $\leq
f$-decomposable form. Thus, using Lemma 2.3, each jump vertex on $P_{i}$ can
be found in $O(f+\log(nW))$ time. Using Lemma 5.3, since there are $\leq
16f\log(nW)$ jump vertices on path $P_{i}$, the total time taken to find
$\textsc{Jump}(P_{i}[s,t])$ and $\textsc{Jump}(P_{i}[t,s])$ is $\leq
cf^{2}\log^{2}(nW)$ (for some suitable constant $c>1$). Thus, the time taken
to find all the jump sequences is
$\leq\underbrace{cf^{3}\log^{2}(nW)}_{\eta}$.

Then, we go over each possible pair $(i,j)\in[1\dots f]\times[1\dots f]$.
There are $\underbrace{f^{2}}_{\beta}$ such pairs. For each pair
$(x,y)\in\textsc{Jump}(P_{i}[s,t])\times\textsc{Jump}(P_{j}[t,s])$, we may
call the function $\textsc{Find-Intermediate}_{1}(x,y,f+1)$. Using Lemma 5.3,
there are $\leq\underbrace{256f^{2}\log^{2}(nW)}_{\gamma}$ possible $(x,y)$
pairs. Using Lemma 8.2, the running time of $\textsc{Find-
Intermediate}_{1}(x,y,f+1)$ is $\underbrace{O(f^{4})}_{\delta}$. Thus, the
total time $Y$ taken by $\textsc{Query}(s,t,r)$ (excluding recursive calls)
is:

$Y\leq\underbrace{10c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}+1}(nW)}_{\alpha}+\underbrace{cf^{3}\log^{2}(nW)}_{\eta}+c\underbrace{f^{2}}_{\beta}\times\underbrace{256f^{2}\log^{2}(nW)}_{\gamma}\times\underbrace{f^{4}}_{\delta}$

The first term on the RHS dominates the rest if we set $c$ to a suitable high
constant. Thus, $Y\leq 12c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}}(nW)$. Let us now
find the total number of recursive calls in $\textsc{Query}(s,t,r)$. The
number of intermediate vertices returned by $\textsc{Find-
Intermediate}_{1}(x,y,r)$ is $\underbrace{8f^{3}}_{\theta}$. For each
intermediate vertex, we call $\textsc{Query}(\cdot,\cdot,r-1)$ two times.
Thus, the total number of recursive calls $X$ can be bounded as:

$X\leq\underbrace{f^{2}}_{\beta}\times\underbrace{256f^{2}\log^{2}(nW)}_{\gamma}\times\underbrace{8f^{3}}_{\theta}\times
2=5096f^{7}\log^{2}(nW)\leq 5096f^{8}\log^{2}(nW)$

Hence, we get the following recurrence relation, $T(r)\leq XT(r-1)+Y$ or

$T(r)\leq
5096f^{8}\log^{2}(nW)T(r-1)+12c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}}(nW)$

Using induction hypothesis, we put $T(r-1)\leq
c^{f^{2}+r-1}f^{8(f^{2}+r-1)}\log^{2(f^{2}+r-1)}(nW)$ in the above equation.
Thus, we get:

$T(r)$ |  $\leq 5096c^{f^{2}+r-1}f^{8(f^{2}+r-1)+8}\log^{2(f^{2}+r-1)+2}(nW)+12c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}}(nW)$
---|---
|  $\leq c^{f^{2}+r}f^{8(f^{2}+r)}\log^{2(f^{2}+r)}(nW)$ (if $c\geq 10192$)

∎

To complete the proof of Theorem 1.1, we prove Lemma 8.2 and Lemma 8.1 in
Section 9 and Section 10 respectively. In Section 11, we bound the space taken
by our oracle.

##  9 Proof of Lemma 8.2

Before looking at the procedure $\textsc{Find-Intermediate}_{1}(x,y,r)$, let’s
first examine the maximisers we will employ within it.

###  9.1 Maximisers

We will use three new maximisers.

First Maximiser: Our first maximiser is as follows:

$\displaystyle\mathbb{D}_{1}(x,y,d_{1},d_{2})=\arg\max_{F^{*}\in
E^{f}}\Biggl{\\{}$ $\displaystyle|xy\diamond F^{*}|\leavevmode\nobreak\
\text{such that the closest vertex of $V(F^{*})$ is at a distance}$
$\displaystyle\text{at least $d_{1}$ from $x$ and $d_{2}$ from $y$ where both
$d_{1}$ and $d_{2}$ are power of 2}\Biggl{\\}}$ (6)

As in Section 6, we assume the maximiser returns $F^{*}$ and the path
$xy\diamond F^{*}$ is in $f+1$-decomposable form. We denote this as
$(F^{*},xy\diamond F^{*})\leftarrow\mathbb{D}_{1}(x,y,d_{1},d_{2})$. The sizes
of $F^{*}$ and $xy\diamond F^{*}$ are both $O(f)$, resulting in a space usage
of $O(f)$ per maximiser. For fixed $x$ and $y$, the total number of maximisers
is $O(\log^{2}(nW))$. Thus, the total space taken by all of $\mathbb{D}_{1}$
maximisers is $\sum_{x,y}O(f\log^{2}(nW))=O(fn^{2}\log^{2}(nW))$.

Second Maximiser: For each vertex $v\in V(F^{*})$ returned by maximiser
$\mathbb{D}_{1}(x,y,d_{1},d_{2})$, we make two maximisers: (1)
$\mathbb{D}_{2}(x,y,d_{1},v)$ and (2) $\mathbb{D}_{2}(x,y,v,d_{2})$. We define
the first maximiser. The definition of the second maximiser is symmetric.

$\displaystyle\mathbb{D}_{2}(x,y,d_{1},v)=\arg\max_{F^{*}\in
E^{f}}\Biggl{\\{}$ $\displaystyle|xy\diamond F^{*}|\leavevmode\nobreak\
\text{such that the closest vertex of $V(F^{*})$ is at a distance}$ at least
$d_{1}$ from $x$ where $d_{1}$ is a power of 2 and $\displaystyle\text{$v$ is
$y$-clean from the failure $F^{*}$}\Biggl{\\}}$ (7)

For $\mathbb{D}_{2}(x,y,v,d_{2})$, in the conditions, $v$ is $x$-clean from
the failures $F^{*}$ and the closest vertex of $V(F^{*})$ is at a distance
$d_{2}$ from $y$. For each maximiser $\mathbb{D}_{1}$, we create $O(f)$
$\mathbb{D}_{2}$ maximisers, each requiring $O(f)$ space. Therefore, the total
space used by all $\mathbb{D}_{2}$ maximisers is $O(f^{2}n^{2}\log(nW))$.

Third Maximiser: For each vertex $u\in V(F^{*})$ returned by maximiser
$\mathbb{D}_{2}(x,y,d_{1},v)$, we make a maximiser $\mathbb{D}_{3}(x,y,u,v)$.

$\displaystyle\mathbb{D}_{3}(x,y,u,v)=\arg\max_{F^{*}\in E^{f}}\Biggl{\\{}$
$\displaystyle|xy\diamond F^{*}|\leavevmode\nobreak\ \text{such that $u$ is
$x$-clean and $v$ is $y$-clean from failure $F^{*}$}\Biggl{\\}}$

Similar is that case for the other variant of $\mathbb{D}_{2}$ maximiser.
Thus, for each maximiser $\mathbb{D}_{2}$, we create $O(f)$ $\mathbb{D}_{3}$
maximisers. The total size of $\mathbb{D}_{3}$ maximisers can be bounded to
$O(f^{3}n^{2}\log(nW))$.

Properties of our maximisers: Whenever we will use our maximisers, we will
ensure that $F$ satisfies their conditions. We will later see all our
maximisers return a set $F^{*}$ with one or more of the following guarantees
for a pair $(x,y)$ that satisfies (S1):

  1. (G1)

$xy\diamond F=xy\diamond F^{*}$.

  2. (G2)

$V(F^{*})$ contains a vertex that is $x$-clean from failure $F$.

  3. (G3)

$V(F^{*})$ contains a vertex that is $y$-clean from failure $F$.

  4. (G4)

$V(F^{*})$ contains an intermediate vertex of $xy\diamond F$.

Let us now go over the cases when these maximisers will be used.

  1. 1.

Maximiser $\mathbb{D}_{1}$ is used when we have neither found an $x$-clean or
$y$-clean vertex.

We will use $\mathbb{D}_{1}$ in our main procedure $\textsc{Find-
Intermediate}_{1}$ (See Section 9.4). The maximiser comes with the following
guarantees: either (G1) or (G2) or (G3) or (G4) is true. Thus, in the worst
case, we will either get an $x$-clean or a $y$-clean vertex from this
maximiser.

  2. 2.

Maximiser $\mathbb{D}_{2}$ is used when we either found an $x$-clean or a
$y$-clean vertex.

Let us assume that we have found a $y$-clean vertex. In procedure
$\textsc{Find-Intermediate}_{2}$ (See Section 9.3), we will use
$\mathbb{D}_{2}$. It comes with the following guarantees: either (G1) or (G2)
or (G4) is true. Thus, in the worst case, we will get an $x$-clean vertex from
this maximiser.

  3. 3.

Maximiser $\mathbb{D}_{3}$ is used when we have found both an $x$-clean and
$y$-clean vertex.

$\mathbb{D}_{3}$ will be used in $\textsc{Find-Intermediate}_{3}$ (See Section
9.2). It comes with the following guarantee: either (G1) or (G4) is true.
Thus, in the worst case, we get an intermediate vertex from this maximiser.

Before we move ahead, we would like the reader to again refresh setting (S1)
as its assumptions will be used in our arguments henceforth. In the setting
(S1), we have assumed that $st\diamond F$ is $r$-decomposable. Also, $x$ and
$y$ lie on the first and the last segment of $st\diamond F$. Thus,

$xy\diamond F$ is also $r$-decomposable. (9)

Let us now go over the above three cases in reverse order.

###  9.2 Found an $x$-clean and a $y$-clean vertex

Let us assume that $u$ is $x$-clean and $v$ is $y$-clean from failure $F$. In
that case, we call the procedure $\textsc{Find-Intermediate}_{3}(x,y,u,v)$
(See Algorithm 4). In this procedure, we will use the maximiser
$\mathbb{D}_{3}(x,y,u,v)$. Note that by definition of a clean vertex, $F$
satisfies the conditions of $\mathbb{D}_{3}$. Let $F^{*}$ be the output of
$\mathbb{D}_{3}(x,y,u,v)$. If $xy\diamond F^{*}$ does not contain any edge
from $F$, we update Path.

1 $(F^{*},xy\diamond F^{*})=\mathbb{D}_{3}(x,y,u,v)$;

2 $\textsc{Intermediate}\leftarrow\emptyset$;

3 if  _$xy\diamond F^{*}$ does not contain any edges of $F$_ then

4 $\textsc{Path}\leftarrow xy\diamond F^{*}$;

5

6for  _$z\in V(F^{*})$_ do

// $z$ satisfies the definition of an intermediate vertex

7 if  _both $xz$ and $zy$ contain an edge from $F$_ then

8 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup\\{z\\}$;

9

10

11

12return $(\textsc{Path},\textsc{Intermediate})$;

Algorithm 4 $\textsc{Find-Intermediate}_{3}(x,y,u,v)$

Then, we go over all $z\in V(F^{*})$. If $z$ satisfies the definition of an
intermediate vertex, then we add it to the Intermediate set. Else, we discard
it.

####  9.2.1 Correctness

We will now show that either (G1) or (G4) is true for $\textsc{Find-
Intermediate}_{3}(x,y,u,v)$. If $F^{*}$ does not hit $xy\diamond F$, then by
Lemma 6.1, (G1) is true. Also, since $xy\diamond F$ is $r$-decomposable (using
Equation 9), we also return it in $r$-decomposable form. So, let us move to
the interesting case when an edge of $F^{*}$ lies in the path $xy\diamond F$.
In this case, we will show that (G4) is true.

######  Lemma 9.1.

If an edge of $F^{*}$, say $e=(z,z^{\prime})$, lies in the path $xy\diamond
F$, then at least one endpoint of $e$, say $z$, is an intermediate vertex.

###### Proof.

To show that $z$ is an intermediate vertex, we have to show it lies neither on
the first segment nor the last segment of $xy\diamond F$. Let us show that $z$
cannot lie on the first segment of $xy\diamond F$.

Since $u$ is $x$-clean from failure $F$, $u$ lies on the first segment of
$xy\diamond F$. By the condition of the maximiser, $u$ is $x$-clean from
failure $F^{*}$ too. Thus, (1) no edge in $F^{*}$ can lie on $xu$ path and (2)
no vertex in $V(F^{*})$ can lie on $T_{x}(u)$.

By (1), $e$ lies after $u$ on $xy\diamond F$. Or, $z$ lies after $u$ on
$xy\diamond F$. By (2), $z$ cannot lie on $T_{x}(u)$.Let us assume that $z$
lies on the first segment of $xy\diamond F$. By (1), it lies after $u$ (as $e$
also lies after $u$). But then $z\in T_{x}(u)$, which is a contradiction.
Thus, $z$ cannot lie on the first segment of $xy\diamond F$. Similarly, we can
show that $z$ cannot lie on the last segment of $xy\diamond F$. Hence, $z$ is
an intermediate vertex.

∎

####  9.2.2 Running time and the size of Intermediate set

The maximiser $\mathbb{D}_{3}$ returns the path $xy\diamond F^{*}$ in $\leq
f+1$ decomposable form, taking $O(f)$ space. Consider any shortest path, say
$ab$, in the decomposition. In $O(f)$ time, we can find if any edge of $F$
lies on $ab$. So it takes $O(f^{2})$ time to check if $xy\diamond F^{*}$
contains any edges from $F.$ To check if a vertex $z$ is an intermediate
vertex, we need to check if $xz$ and $yz$ contains any edge from $F$. Again,
this takes $O(f)$ time. Thus, the running time of $\textsc{Find-
Intermediate}_{3}(x,y,u,v)$ is $O(f^{2})$. Also, we can add at most $2f$
vertices in Intermediate. Thus, we claim the following lemma:

######  Lemma 9.2.

The running time of $\textsc{Find-Intermediate}_{3}(x,y,u,v)$ is $O(f^{2})$
and the size of Intermediate set returned by it is $\leq 2f$.

###  9.3 Found a $y$-clean vertex

Let us assume that we have found a vertex $v$ that is $y$-clean from the
failure $F$. In that case, we call the function $\textsc{Find-
Intermediate}_{2}(x,y,\phi,v)$. The third parameter of this function indicates
that we have not found any $x$-clean vertex, and the fourth parameter is the
$y$-clean vertex.

We now describe function $\textsc{Find-Intermediate}_{2}(x,y,\phi,v)$ (See
Algorithm 5). In this function, we will calculate $d_{1}$, the largest power
of 2 no more than the distance of the closest vertex of $V(F)$ from $x$. Then,
we use the maximiser $\mathbb{D}_{2}(x,y,d_{1},v)$. The reader can check that
$F$ satisfies the conditions of maximiser. Let $F^{*}$ be the edges returned
by $\mathbb{D}_{2}(x,y,d_{1},v)$. If $xy\diamond F^{*}$ does not contain any
edge from $F$, we update Path. Then, we go over all vertices $u\in V(F^{*})$.
If $u$ satisfies the condition of being an $x$-clean vertex, then we call
function $\textsc{Find-Intermediate}_{3}(x,y,u,v)$. If $u$ satisfies the
definition of an intermediate vertex, then we add it to the Intermediate set.
Else, we discard $u$. Before moving forward, let us state an important
observation which implies that in $\textsc{Find-Intermediate}_{3}$ we are
using maximisers that are created in Section 9.1.

######  Remark 9.3.

In $\textsc{Find-Intermediate}_{3}(x,y,u,v)$, we will use maximiser
$\mathbb{D}_{3}(x,y,u,v)$ which is one of the $O(f)$ maximisers created from
$\mathbb{D}_{2}(x,y,d_{1},v)$.

1 $d_{1}=\min_{a\in V(F)}\\{(xa)_{2}\\}$;

2 $(F^{*},xy\diamond F^{*})=\mathbb{D}_{2}(x,y,d_{1},v)$ ;

3 $\textsc{Intermediate}\leftarrow\emptyset$;

4 if  _$xy\diamond F^{*}$ does not contain any edges of $F$_ then

5 $\textsc{Path}\leftarrow xy\diamond F^{*}$;

6

7for  _$u\in V(F^{*})$_ do

// $u$ satisfies the definition of an $x$-clean vertex

8 if  _$xu$ and $T_{u}(x)$ is intact from failure $F$_ then

9 $(P,I)\leftarrow\textsc{Find-Intermediate}_{3}(x,y,u,v)$;

10 $\textsc{Path}\leftarrow\text{argmin}\\{|P|,|\textsc{Path}|\\}$;

11 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup I$;

12

//  $u$ satisfies the definition of an intermediate vertex

13 if  _both $xu$ and $yu$ contain a failure from $F$_ then

14 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup\\{u\\}$;

15

16

17

18return $(\textsc{Path},\textsc{Intermediate})$;

Algorithm 5 $\textsc{Find-Intermediate}_{2}(x,y,\phi,v)$

####  9.3.1 Correctness

We will now show that either (G1) or (G2) or (G4) is true for $\textsc{Find-
Intermediate}_{2}(x,y,\phi,v)$. Let $(F^{*},xy\diamond F^{*})$ be the output
of the maximiser $\mathbb{D}_{2}(x,y,d_{1},v)$. If $F^{*}$ does not hit
$xy\diamond F$, then by Lemma 6.1, (G1) is true. Also, since $xy\diamond F$ is
$r$-decomposable (using Equation 9), we also return it in $r$-decomposable
form. Let us now move to the interesting case when an edge of $F^{*}$, say
$e$, lies on $xy\diamond F$. Or an endpoint of $e$, say $u$, lies on the path
$xy\diamond F$. There are three cases:

  1. (Case I)

$u$ is an intermediate vertex.

If $u$ is an intermediate vertex, then (G4) is true.

  2. (Case II)

$u$ lies on the last segment of $xy\diamond F$.

We will show that this case cannot arise. Our argument is similar to the one
given in the proof of Lemma 9.1. The vertex $v$ is $y$-clean from failure $F$
so, $v$ lies on the last segment of $xy\diamond F$. Since $F^{*}$ also
satisfies the condition of the maximiser, $v$ is $y$-clean from failure
$F^{*}$ too. Thus, (1) no edge in $F^{*}$ can lie on $yv$ path and (2) no
vertex in $V(F^{*})$ can lie on $T_{y}(v)$. By (1), $e$ cannot lie on the last
segment of $xy\diamond F$. By (2), $u$ cannot lie in $T_{y}(v)$. As in the
proof of Lemma 9.1, if $u$ is in the last segment of $xy\diamond F$, then by
(1), it lies after $v$. But then $u\in T_{y}(v)$, which is a contradiction.
This implies that $u$ cannot lie on the last segment of $xy\diamond F$.

  3. (Case III)

$u$ lies on the first segment of $xy\diamond F$.

We will show that $u$ must be an $x$-clean vertex. Thus, (G2) is true. To
prove $u$ is $x$-clean, we have to show that:

    1. (P1)

$xu$ is intact from failure $F$ and

    2. (P2)

$T_{x}(u)$ is intact from failure $F$.

Since $u$ lie on the first segment of $xy\diamond F$, (Case III)(P1) is true.
We now prove (Case III)(P2). Let us look back at the setting which led us to
call $\textsc{Find-Intermediate}_{2}(x,y,\phi,v)$. To this end, we encourage
the reader to see Setting (S1) again as we will be using it in the ensuing
argument.

Let $R=st\diamond F$. In $\textsc{Find-Intermediate}_{2}(x,y,\phi,v)$, we set
$d_{1}=\min_{a\in V(F)}\\{(xa)_{2}\\}$. Since, the detour of $R$ starts at the
vertex $p$ on the path $P_{i}$, and $x$ is the last vertex of
$\textsc{Jump}(P_{i}[s,t])$ before $p$ on the path $P_{i}$, we have:

$P_{i}[x,p]<d_{1}$

Again, since the detour of $R$ starts at the vertex $p$ on the path $P_{i}$
and $x$ lies before $p$ on path $P_{i}$, we can write the above equation as:

$R[x,p]<d_{1}$ (10)

But according to the condition in $\mathbb{D}_{2}(x,y,d_{1},v)$, $u$ must be
at a distance $\geq d_{1}$ from $x$. Since $u$ lies on the first segment of
$xy\diamond F$ (by the assumption in this case) and $x$ lies on the first
segment of $R$ (by assumption in (S1)), we have:

$R[x,u]\geq d_{1}$ (11)

Thus, using Equation 10 and Equation 11, $u$ lies after $p$ on $R$ (See Figure
4 for an illustration). But the detour of $R$ starts at $p$ on $P_{i}$ (by
assumption in (S1)). This implies the following:

$u$ lies on path $R$ but not on $P_{i}[s,t]$ (12)

$s$$t$$R$$P_{i}$$p$$x$$u$ Figure 4: $u$ can lie only on the violet subpath of
$R$. The horizontal black path is $P_{i}$.

Some remarks are in order. The above statement is one of the most important
deductions in our paper. We are able to prove that $u$ does not lie on $P_{i}$
but lies on the detour of $R$. This will help us in proving that $u$ satisfies
(Case III)(P2).

We will now show that $T_{x}(u)$ contains no endpoints from $V(F)$. For
contradiction, let $e_{k}=(a_{k},b_{k})$ be the faulty edge whose endpoint is
nearest to $u$ in $T_{x}(u)$. Remember that we have found $f$ paths
$P_{1},P_{2},\dots,P_{f}$ using FindPath. Let us assume that $e_{k}$ is the
first edge on $P_{k}[s,t]$ and $a_{k}$ is closer to $s$ on $P_{k}$. There are
two cases depending on whether $P_{k}=P_{i}$ or not.

    1. (a)

$P_{k}=P_{i}$ and $e_{k}=e_{i}$

We will show that neither $a_{i}$ nor $b_{i}$ lies in $T_{x}(u)$.

      1. i.

$a_{i}$ cannot lie in $T_{x}(u)$

Since $u$ lies on the first segment of $xy\diamond F$ (by assumption in this
case), and $x$ lies on the first segment of $R$ (by assumption in (S1)),
$sa_{i}$ avoids $F$ and the shortest path from $s$ to $e_{i}$ passes through
$u$. Or, $P_{i}[s,t]$ passes through $u$. But this contradicts Equation 12
(See Figure 5 for an illustration).

      2. ii.

$b_{i}$ cannot lie in $T_{x}(u)$

If $b_{i}$ is nearest to $u$ in $T_{x}(u)$, then the path $sb_{i}$ avoids $F$.
But then there is a shorter path from $s$ to $b_{i}$ that avoids $e_{i}$. This
is $su\odot ub_{i}$. Thus, $P_{i}[s,b_{i}]$ does not pass through $e_{i}$, a
contradiction.

$u$$a_{i}$$b_{i}$$s$$t$$x$$P_{i}$$R$ Figure 5: If $a_{i}\in T_{x}(u)$, then
$P_{i}[s,t]$ contains $u$ and this contradicts Equation 12.

    2. (b)

$P_{k}\neq P_{i}$

We will show that neither $a_{k}$ nor $b_{k}$ lies in $T_{x}(u)$.

      1. i.

$a_{k}$ cannot lie in $T_{x}(u)$

If $a_{k}$ is the nearest vertex to $u$ in $T_{x}(u)$, then $sa_{k}$ avoids
$F$. So, $se_{k}=su\odot ue_{k}$. Since, the shortest $se_{k}$ path contains
$u$, $P_{k}$ also passes through $u$. Now, by Equation 12, $u$ does not lie on
$P_{i}[s,t]$ but $R$ passes through $u$. But then the detour of $R$ must start
on that path $P_{k}$ after the vertex $u$ (See Figure 6 for an illustration).
This is a contradiction as we assumed that the detour of $R$ starts on path
$P_{i}$ in Setting (S1).

      2. ii.

$b_{k}$ cannot lie in $T_{x}(u)$

If $b_{k}$ is nearest to $u$ in $T_{x}(u)$, then our arguments are the same as
in Case (a)(ii).

Thus, $u$ satisfies (Case III)(P2) and it is an $x$-clean vertex.

$u$$a_{k}$$b_{k}$$s$$t$$x$$P_{i}$$P_{k}$$R$ Figure 6: Here the blue path is
$P_{i}$. $su$ is intact from failure $F$ and is in the first segment of $R$.
So, the detour of $R$ starts somewhere in the dashed path from $u$ to $a_{k}$.
Or the detour starts on $P_{k}$. This contradicts our assumption in (S1) that
the detour starts on $P_{i}$.

####  9.3.2 Running time and the size of Intermediate set

The running time is dominated by Algorithm 5 of $\textsc{Find-
Intermediate}_{2}(x,y,\phi,v)$. In this line, the procedure $\textsc{Find-
Intermediate}_{3}(x,y,u,v)$ is invoked. But this invocation can happen only
$O(f)$ times. Using Lemma 9.2, the running time of $\textsc{Find-
Intermediate}_{3}(xy,u,v)$ is $O(f^{2})$. Thus, the running time of
$\textsc{Find-Intermediate}_{2}(x,y,\phi,v)$ is $O(f^{3})$. Moreover,
$\textsc{Find-Intermediate}_{3}(xy,u,v)$ returns $2f$ candidate intermediate
vertices. Thus, in the worst case, we can add at most $4f^{2}$ vertices in
Intermediate. Thus, we claim the following lemma:

######  Lemma 9.4.

The running time of $\textsc{Find-Intermediate}_{2}$ is $O(f^{3})$, and the
size of Intermediate set returned by it is $\leq 4f^{2}$.

###  9.4 Neither found an $x$-clean or a $y$-clean vertex

1 $d_{1}=\min_{a\in V(F)}\\{(xa)_{2}\\}$;

2 $d_{2}=\min_{a\in V(F)}\\{(ay)_{2}\\}$;

3 $(F^{*},xy\diamond F^{*})=\mathbb{D}_{1}(x,y,d_{1},d_{2})$ ;

4 $\textsc{Path}\leftarrow\emptyset$;

5 $\textsc{Intermediate}\leftarrow\emptyset$;

6 if  _$xy\diamond F^{*}$ does not contain any edge of $F$_ then

7 $\textsc{Path}\leftarrow xy\diamond F^{*}$;

8

9for  _$u\in V(F^{*})$_ do

// $u$ satisfies the conditions of an $x$-clean vertex

10 if  _$xu$ and $T_{u}(x)$ is intact from failure $F$_ then

11 $(P_{1},I_{1})\leftarrow\textsc{Find-Intermediate}_{2}(x,y,u,\phi)$;

12 $\textsc{Path}\leftarrow\text{argmin}\\{|P_{1}|,|\textsc{Path}|\\}$;

13 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup I_{1}$;

14

// $u$ satisfies the conditions of a $y$-clean vertex

15 if  _$yu$ and $T_{u}(y)$ is intact from failure $F$_ then

16 $(P_{2},I_{2})\leftarrow\textsc{Find-Intermediate}_{2}(x,y,\phi,u)$;

17 $\textsc{Path}\leftarrow\text{argmin}\\{|P_{2}|,|\textsc{Path}|\\}$;

18 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup I_{2}$;

19

// $u$ satisfies the conditions of an intermediate vertex

20 if  _$xu$ and $T_{u}(x)$ is intact from failure $F$_ then

21 $\textsc{Intermediate}\leftarrow\textsc{Intermediate}\cup\\{u\\}$;

22

23

24

25return $(\textsc{Path},\textsc{Intermediate})$;

26

Algorithm 6 $\textsc{Find-Intermediate}_{1}(x,y,r)$

This is the most general case in which we call $\textsc{Find-
Intermediate}_{1}(x,y,r)$. Let us describe this function (See Algorithm 6). We
first find the distance of the closest vertex of $V(F)$ from $x$ and $y$. That
is, we set $d_{1}=\min_{a\in V(F)}\\{(xa)_{2}\\}$ and $d_{2}=\min_{a\in
V(F)}\\{(ya)_{2}\\}$. Then, we use the maximiser
$\mathbb{D}_{1}(x,y,d_{1},d_{2})$. First, note that $F$ satisfies the
condition of the maximiser.

Let $F^{*}$ be the edges returned by $\mathbb{D}_{2}(x,y,d_{1},d_{2})$. If
$xy\diamond F^{*}$ does not contain any edge from $F$, we update Path. Then,
we go over all vertices $u\in V(F^{*})$. If $u$ satisfies the conditions of an
$x$-clean vertex, then we call the function $\textsc{Find-
Intermediate}_{2}(x,y,u,\phi)$. Similar is the case when $u$ is a potential
$y$-clean vertex. Else, if $u$ satisfies the conditions of an intermediate
vertex, then we add it to Intermediate set. Else, we discard $u$.

As in the previous section, we claim the maximisers $\mathbb{D}_{2}$ used by
us in $\textsc{Find-Intermediate}_{2}(x,y,u,\phi)$ are created from
$\mathbb{D}_{1}$ maximisers.

######  Remark 9.5.

In $\textsc{Find-Intermediate}_{2}(x,y,u,\phi)$, we will use maximiser
$\mathbb{D}_{2}(x,y,u,d_{2})$ which is one of the $O(f)$ maximisers created
from $\mathbb{D}_{1}(x,y,d_{1},d_{2})$. Similarly, in $\textsc{Find-
Intermediate}_{2}(x,y,\phi,u)$, we will use maximiser
$\mathbb{D}_{2}(x,y,d_{1},u)$ which is one of the $O(f)$ maximisers created
from $\mathbb{D}_{1}(x,y,d_{1},d_{2})$.

####  9.4.1 Correctness

We will now show that at least one of the guarantees from (G1) to (G4) is
true. Let $(F^{*},xy\diamond F^{*})$ be the tuple returned by the maximiser
$\mathbb{D}_{1}$ in $\textsc{Find-Intermediate}_{1}(x,y,r)$. If $F^{*}$ does
not hit $xy\diamond F$, then by Lemma 6.1, (G1) is true. Let us now move to
the interesting case when an edge of $F^{*}$, say $e$, lies on $xy\diamond F$.
Or an endpoint of $e$, say $u$, lies on the path $xy\diamond F$. There are
three cases:

  1. 1.

$u$ is an intermediate vertex.

In this case, (G4) is true.

  2. 2.

$u$ lies on the first segment of $xy\diamond F$.

In this case, we can show that $u$ is an $x$-clean vertex or (G2) is true. Our
arguments are identical to the one used in (Case III).

  3. 3.

$u$ lies on the last segment of $xy\diamond F$.

By symmetry, we claim that $u$ is a $y$-clean vertex or (G3) holds.

####  9.4.2 Running time and the size of Intermediate set

The running time of function $\textsc{Find-Intermediate}_{1}(x,y,r)$ is
dominated by the number of times we call Algorithm 6 or Algorithm 6 . Note
that either Algorithm 6 or Algorithm 6 is executed in each iteration of the
for loop. Wlog, let us assume that Algorithm 6 is executed in each iteration.
In Algorithm 6, the procedure $\textsc{Find-Intermediate}_{2}(x,y,\phi,u)$ is
invoked. But this can happen only $O(f)$ time. Using Lemma 9.4, running time
of $\textsc{Find-Intermediate}_{2}(x,y,\phi,u)$ is $O(f^{3})$. Thus, running
time of $\textsc{Find-Intermediate}_{1}(x,y,r)$ is $O(f^{4})$. Moreover,
$\textsc{Find-Intermediate}_{2}(x,y,\phi,u)$ returns $4f^{2}$ candidate
intermediate vertices. Thus, in the worst case, we can add at most $8f^{3}$
vertices in Intermediate. Thus, we claim the following lemma:

######  Lemma 9.6.

The running time of $\textsc{Find-Intermediate}_{1}(x,y,r)$ is $O(f^{4})$ and
the size of Intermediate set returned by it is $\leq 8f^{3}$.

###  9.5 Summary of the the proof of Lemma 8.2

If the pair $(x,y)$ satisfies (S1), then we can use our discussion in the
above three sections. In
$\textsc{Find-Intermediate}_{1}(x,y,r)$, in the best case, we find $xy\diamond
F$ and return it. Or, we find an intermediate vertex. But in the worst case,
we either find an $x$-clean or a $y$-clean vertex. Let us assume that we find
a $y$-clean vertex $v$. Again, in $\textsc{Find-
Intermediate}_{2}(x,y,\phi,v)$, in the worst case, we find an $x$-clean vertex
$u$. And lastly, in $\textsc{Find-Intermediate}_{3}(x,y,u,v)$, we are sure to
find an intermediate vertex in the worst case. Thus, we either return the path
$xy\diamond F$ (in the best case) or a set Intermediate which contains an
intermediate vertex of $xy\diamond F$(in the worst case). Moreover, in the
best case we return $xy\diamond F$ in $r$-decomposable form. Thus, we have
satisfied all the requirement of Lemma 8.2 when the pair $(x,y)$ satisfy
setting (S1).

Let us now discuss the other guarantees in Lemma 8.2 which donot assume
Setting (S1). In algorithm $\textsc{Find-Intermediate}_{1},\textsc{Find-
Intermediate}_{2}$ and $\textsc{Find-Intermediate}_{3}$, before we update
Path, we always check if the path contains $F$ or not. Thus, the Path returned
by $\textsc{Find-Intermediate}_{1}(x,y,r)$ avoids $F$. Using Lemma 9.6, the
running time of $\textsc{Find-Intermediate}_{1}(x,y)$ is $O(f^{4})$ and the
size of Intermediate set is $\leq 8f^{3}$. Thus, we have proven all the
requirements of Lemma 8.2.

##  10 Proof of Lemma 8.1

We use Algorithm 7 to find $P_{1},\dots,P_{f}$. $P_{1}$ is the $st$ path. For
notational convenience, we assume that a “0-fault tolerant” distance oracle
finds the path $P_{1}$. To find $P_{i}$ ($i\geq 2$), using induction
hypothesis, we use the $(i-1)$-fault tolerant distance oracle, which returns
it in $i$-decomposable form. If $P_{i}$ does not contain any faulty edge, then
we can return $P_{i}$ as the answer and exit the query algorithm.

To check if $P_{i}$ contains an edge $e\in F$ or not, we just need four more
invocation of $(i-1)$-distance oracle, two times in Algorithm 7 and Algorithm
7. Thus, we invoke the $i-1$-fault tolerant distance oracle at most $5f$ times
in the $i$-th iteration of the for loop. Thus, the time taken in the $i$-th
iteration of the for loop can be bounded to
$<5fc^{i^{2}}i^{8i^{2}}\log^{2i^{2}}(nW)$. Summing it over all $i$, the
running time of FindPaths is
$\sum_{i=1}^{f}5fc^{i^{2}}i^{8i^{2}}\log^{2i^{2}}(nW)\leq
10c^{f^{2}}f^{8f^{2}+1}\log^{2f^{2}}(nW)$ (if we set $c\geq 2$). This proves
Lemma 8.1.

1 $F^{\prime}\leftarrow\emptyset$;

2

3for  _$i=1$ to $f$_ do

4 $P_{i}\leftarrow st\diamond F^{\prime}$ found using an $i-1$-fault distance
oracle;

5 foreach  _$e\in F-F^{\prime}$_ do

6 $flag\leftarrow 0$;

7 $R_{1}\leftarrow se\diamond F^{\prime}$ found using $i-1$-fault tolerant
distance oracle;

8 $R_{2}\leftarrow et\diamond F^{\prime}$ found using $i-1$-fault tolerant
distance oracle;

//  Check if $e$ lies on the path $P_{i}$

9 if  _$|R_{1}|+w(e)+|R_{2}|=|st\diamond F^{\prime}|$_ then

10 $F^{\prime}\leftarrow F^{\prime}\cup\\{e\\}$;

11 $flag\leftarrow 1$;

12 break;

13

14

15 if  _$flag=0$_ then

16 $P_{i}$ is our answer;

17 exit;

18

19 return $\\{P_{1},P_{2},\dots,P_{f}\\}$

20

Algorithm 7 FindPaths$(s,t,F)$

##  11 Space taken by our oracle

In Section 9.1, we defined maximisers $\mathbb{D}_{1}$, $\mathbb{D}_{2}$, and
$\mathbb{D}_{3}$. The combined size of these maximisers is
$O(f^{3}n^{2}\log^{2}(nW))$. In FindPath, we employ an $i$-fault tolerant
distance oracle, which also utilizes maximisers $\mathbb{D}_{1}$,
$\mathbb{D}_{2}$, and $\mathbb{D}_{3}$. However, the size of these maximisers
is $O(i^{3}n^{2}\log^{2}(nW)$) as here the fault set is of size $i$. For each
$1\leq i\leq f$, these three maximisers are constructed only once. Therefore,
the overall space required for our maximisers is
$O\left(\sum_{i=1}^{f}i^{3}n^{2}\log(nW)\right)=O(f^{4}n^{2}\log^{2}(nW))$.

## References

  * [ABK+02] Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, and Michael Merritt.  Restoration by path concatenation: fast recovery of MPLS paths.  Distributed Computing, 15(4):273–283, 2002.
  * [AW21] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. SIAM, 2021.
  * [BCC+23] Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck.  Approximate distance sensitivity oracles in subquadratic space.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1396–1409, 2023.
  * [BK08] Aaron Bernstein and David R. Karger.  Improved distance sensitivity oracles via random sampling.  In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 34–43. SIAM, 2008.
  * [BK09a] Aaron Bernstein and David Karger.  A nearly optimal oracle for avoiding failed vertices and edges.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 101–110. ACM, 2009.
  * [BK09b] Aaron Bernstein and David Karger.  A nearly optimal oracle for avoiding failed vertices and edges.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 101–110, 2009.
  * [BK13] Surender Baswana and Neelesh Khanna.  Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs.  Algorithmica, 66:18–50, 2013.
  * [CC20] Shiri Chechik and Sarel Cohen.  Distance sensitivity oracles with subcubic preprocessing time and fast query time.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1375–1388, 2020.
  * [CCFK17] Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan.  (1 + $\epsilon$)-approximate _f_ -sensitive distance oracles.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1479–1496, 2017.
  * [Cha05] Timothy M Chan.  All-pairs shortest paths with real weights in o (n 3/log n) time.  In Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005. Proceedings 9, pages 318–324. Springer, 2005.
  * [Cha07] Timothy M Chan.  More algorithms for all-pairs shortest paths in weighted graphs.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 590–598, 2007.
  * [Cha08] Timothy M Chan.  All-pairs shortest paths with real weights in o (n 3/log n) time.  Algorithmica, 50:236–243, 2008.
  * [CW87] Don Coppersmith and Shmuel Winograd.  Matrix multiplication via arithmetic progressions.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 1–6, 1987.
  * [Dob90] Wlodzimierz Dobosiewicz.  A more efficient algorithm for the min-plus multiplication.  International journal of computer mathematics, 32(1-2):49–60, 1990\.
  * [DP09] Ran Duan and Seth Pettie.  Dual-failure distance and connectivity oracles.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 506–515, 2009.
  * [DR22] Ran Duan and Hanlin Ren.  Maintaining exact distances under multiple edge failures.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 1093–1101. ACM, 2022.
  * [DTCR08] Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran.  Oracles for distances avoiding a failed node or link.  SIAM J. Comput., 37(5):1299–1318, 2008.
  * [Flo67] Robert W Floyd.  Algorithm 97.  Comm. ACM, 5:345, 1967.
  * [Fre76] Michael L Fredman.  New bounds on the complexity of the shortest path problem.  SIAM Journal on Computing, 5(1):83–89, 1976.
  * [Gal14] François Le Gall.  Powers of tensors and fast matrix multiplication.  In International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014, pages 296–303, 2014\.
  * [GR21] Yong Gu and Hanlin Ren.  Constructing a distance sensitivity oracle in ${O}(n^{2.5794}{M}$) time.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 76:1–76:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [GS18] Manoj Gupta and Aditi Singh.  Generic single edge fault tolerant exact distance oracle.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 72:1–72:15, 2018.
  * [GW19] Fabrizio Grandoni and Virginia Vassilevska Williams.  Faster replacement paths and distance sensitivity oracles.  ACM Transactions on Algorithms (TALG), 16(1):1–25, 2019.
  * [Han04] Yijie Han.  Improved algorithm for all pairs shortest paths.  Information Processing Letters, 91(5):245–250, 2004.
  * [Han06] Yijie Han.  An o (n 3 (loglog n/log n) 5/4) time algorithm for all pairs shortest paths.  In European Symposium on Algorithms, pages 411–417. Springer, 2006\.
  * [Han08] Yijie Han.  An o (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path.  Algorithmica, 51:428–434, 2008.
  * [HS01] John Hershberger and Subhash Suri.  Vickrey prices and shortest paths: What is an edge worth?  In Proceedings 42nd IEEE symposium on foundations of computer science, pages 252–259. IEEE, 2001.
  * [KS23] Adam Karczmarz and Piotr Sankowski.  Sensitivity and dynamic distance oracles via generic matrices and frobenius form.  In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, 2023.
  * [PP13] Merav Parter and David Peleg.  Sparse fault-tolerant bfs trees.  In European Symposium on Algorithms, pages 779–790. Springer, 2013\.
  * [Sto10] Andrew James Stothers.  On the complexity of matrix multiplication.  2010\.
  * [Tak92] Tadao Takaoka.  A new upper bound on the complexity of the all pairs shortest path problem.  Information Processing Letters, 43(4):195–199, 1992.
  * [Tak04] Tadao Takaoka.  A faster algorithm for the all-pairs shortest path problem and its application.  In Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004. Proceedings 10, pages 278–289. Springer, 2004.
  * [Tak05] Tadao Takaoka.  An o (n3loglogn/logn) time algorithm for the all-pairs shortest path problem.  Information Processing Letters, 96(5):155–161, 2005.
  * [vdBS19] Jan van den Brand and Thatchaphol Saranurak.  Sensitive distance and reachability oracles for large batch updates.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 424–435. IEEE Computer Society, 2019.
  * [War62] Stephen Warshall.  A theorem on boolean matrices.  Journal of the ACM (JACM), 9(1):11–12, 1962.
  * [Wil12] Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887–898, 2012.
  * [Wil14] Ryan Williams.  Faster all-pairs shortest paths via circuit complexity.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 664–673, 2014.
  * [WY13] Oren Weimann and Raphael Yuster.  Replacement paths and distance sensitivity oracles via fast matrix multiplication.  ACM Trans. Algorithms, 9(2), March 2013.
  * [Zwi04] Uri Zwick.  A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths.  In International Symposium on Algorithms and Computation, pages 921–932. Springer, 2004.

##  Appendix A Proof of Lemma 2.3

Let $x$ be the first vertex at a distance $\geq 2^{i}$ from $s$ on $P[s,t]$.
Since $P[s,t]$ is in $f$-decomposable form, let us assume that it is
represented as $L_{1}\odot e_{1}\odot L_{2}\odot\dots\odot e_{f-1}\odot
L_{f}$, where each $L_{i}$ is a shortest path. Since we know the weights of
these paths and interleaving edges, we can efficiently identify the segment
$L_{i}$ containing $x$. Let $L_{i}$ represent the shortest path $pq$. Suppose
we’ve determined that $x$ is at least distance $d$ from $p$.

If $d$ is a power of 2, we can use information stored at vertex $q$ in the
tree $T_{p}$ to find $x$. Else, let $\ell$ be such that $2^{\ell}\leq
d<2^{\ell+1}$. Then we locate the vertex at a distance $\geq 2^{\ell}$-th on
the $pq$ path, denoting it as $p_{1}$. We then recursively examine the path
$p_{1}q$.

In a maximum of $\log(nW)$ recursive steps, we can identify $x$. Initially, it
takes $O(f)$ time to find the shortest path $L_{i}$, and then an additional
$\log(nW)$ time to locate $x$ on $L_{i}$. Therefore, the overall time
complexity is $O(f+\log(nW))$.