We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set $F$ of two edges, as well as a source node $s$ and a destination node $t$, our oracle returns the length of the shortest path from $s$ to $t$ that avoids $F$ in $O(1)$ time with a high probability. The space complexity of our oracle is $\Tilde{O}(n^2)$ [$\Tilde{O}$ hides poly$\log n$ factor ], making it nearly optimal in terms of both space and query time.

Prior to our work, Pettie and Duan [SODA 2009] designed a dual fault-tolerant distance oracle that required $\Tilde{O}(n^2)$ space and $O(\log n)$ query time. In addition to improving the query time, our oracle is much simpler than the previous approach.

§ INTRODUCTION

Graph theory is a valuable tool for modelling and solving many real-world problems. As real-world networks are susceptible to failures, such as faulty edges or vertices within the network, we must design a system that continues to operate in the presence of failures. In this paper, we focus on developing algorithms that effectively operate in the presence of faults. Consider the scenario where we aim to determine the shortest path from a source vertex to a destination vertex. However, we become aware that one of the edges in the graph is unavailable or faulty due to some reasons. Under these circumstances, our objective becomes finding an alternative shortest path that avoids the faulty edge.

Let us describe an abstract model in which we want to solve the above problem. We consider an undirected and unweighted graph, denoted as $G$. To facilitate efficient query processing, we preprocess this graph to construct a suitable data structure. This data structure is used to answer queries about shortest paths in $G$ in the presence of faults.
We assume that we will receive queries of the following form:

$\QU (s,t,F)$: Find length of the shortest path between vertices $s$ and $t$ in graph $G$, avoiding set of edges $F$.

The objective of our algorithm is to efficiently answer the above query by utilising the prepared data structures. After creating a data structure, while queried about $\QU(s,t,F)$, we run an algorithm (named query algorithm) to answer the query. This combination of data structure and query algorithm is commonly referred to as an oracle. Our paper focuses on calculating distances in the presence of faults. Consequently, we refer to our oracle as a fault-tolerant distance oracle.

We evaluate the fault-tolerant distance oracle based on two key parameters: (1) the space required by the data structure and (2) the query time, which refers to the time taken to respond to a query.
To facilitate the description of our results in this context, we introduce a simple notation. We define a distance oracle that avoids a fault set of size at most $f$ as $\DO(f)$. When the source vertex $s$ is fixed in the  $\QU$, the oracle is referred to as a Single Source Distance Oracle or $\SDO(f)$ for brevity.

In this paper, our focus is designing  $\DO(2)$ – i.e., designing fault-tolerant distance oracle that can handle fault set of size at most 2.
We discuss the previous results obtained in this area in <Ref>.

Oracle     Space    Query time     Remarks     Ref

$\DO(1)$     $\TL(n^2)$     $O(1)$    -   <cit.>

$\DO(2)$     $\TL(n^2)$     $O(\log n)$    -   <cit.>

$\DO(f)$     $\TL(n^{3- \alpha})$      $\TL(n^{2-(1- \alpha)/f })$     $\alpha \in [0,1]$ when the preprocessing time  is $O(Mn^{3.376 - \alpha})$ and  edge weights are integral in the range $[-M, \dots , M].$     <cit.>

$\DO(f)$     $\TL(n^{2+\alpha})$     $O(n^{2-\alpha}f^2 + n f^{\omega})$     $\alpha \in [0,1]$ and $\omega $ is the matrix multiplication exponent <cit.>    <cit.>

$\DO(f)$     $O(fn^4)$     $O(f^{O(f)})$    -   <cit.>

$f$     $O(n^2)$     $\TL(nf^{\omega})$     Edge weights are in the range $[1\dots  W]$     <cit.>

$f$     $O(f^4 n^2 \log \NW)$     $O(c^{(f+1)^2}f^{8(f+1)^2}\log^{2(f+1)^2} \NW)$     Edge weights are in the range $[1\dots  W]$     <cit.>

Relevant results for fault-tolerant distance oracles

For $\DO(2)$, the oracle of Pettie and Duan <cit.> is nearly optimal. It takes $\TL(n^2)$ space and $O(\log n)$ query time. However, as the authors of  <cit.> also mentioned, their approach is overly complicated and requires extensive case analysis. Duan and Ren <cit.> proposed a fundamentally different approach. They designed an algorithm for $\DO(f)$ that takes $O(n^4)$ space and $O(f^{O(f)})$ query time. For $\DO(2)$, their query time is $O(1)$. Unlike <cit.>, the main feature of their algorithm is that it involves a limited amount of case analysis. However, the space taken by their algorithm is $O(n^4)$. Recently, Dey and Gupta <cit.> designed an $f$-fault tolerant distance oracle with $\TL(n^2)$ space and $\TL(1)$ query time for fixed $f$. In this paper, using an approach similar to <cit.> and <cit.>, we design a dual-fault tolerant oracle with $\TL(n^2)$ size and $O(1)$ query time. We use some randomisation techniques which helps us to reduce the query time. The main result of this paper is:

For an undirected and unweighted graph, there is a dual fault-tolerant oracle that takes $\TL(n^2)$ space and answers each query in $O(1)$ time with high probability.

Unfortunately, some tools we use in this paper do not works for weighted graphs.

§.§ Related works

Demetrescu et al.<cit.> designed a $\DO(1)$ in $O(mn^2+n^3 \log n)$ construction/preprocessing time (the time required to construct the oracle before taking any query) with  $\TL(n^2)$ space and $O(1)$ query time. Bernstein and Karger  improved the preprocessing time  to $\TL(n^2 \sqrt{m})$ in <cit.> and later   to $\TL(mn)$ time in <cit.>. The preprocessing times of the above results are $\Omega(n^3)$. Grandoni and Williams <cit.> designed the first  $\DO(1)$ with subcubic preprocessing time and sublinear query time. Chechik and Cohen <cit.> kept the preprocessing time as subcubic but improved the query time to $\TL(1)$. After that,  Gu and Ren <cit.> constructed a $\DO(1)$ with $O(n^{2.6146}M)$ preprocessing time and constant query time where $M$ is the maximum edge weight.

Gupta and Singh <cit.> designed an $\SDO(1)$ with $\TL(n\sqrt n)$ space and $\TL(1)$ query time. However, they did not mention the time taken to construct the oracle in their paper. Bilò et al.<cit.> designed an $\SDO(1)$ with $\TL(m \sqrt{n}+n^2)$ preprocessing time. Dey and Gupta <cit.> improved the preprocessing time to $\TL(m \sqrt{n})$.

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 <cit.> designed $(1+\epsilon)$-approximation oracle for both $\DO(1)$ and $\SDO(1)$. Their $\SDO(1)$ oracle required $O(n/ \epsilon^3 + n \log n)$ space.  For multiple faults, Chechik et al.<cit.> designed a $(1+\epsilon)$-approximate $\DO(f)$, 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.<cit.> designed a $(3+\EP)$-approximate distance oracle in sub-quadratic space and sublinear query time.

§ OVERVIEW

In this section, we will at first give an overview of the method used by Duan and Ren in <cit.> to create an $f$-fault tolerant distance oracle with $O(n^4)$ size. After that, we will give an overview of our modifications to that approach to have an oracle for dual faults with $\TL(n^2)$ size and constant query time. For that, let us define some notations at first. The notation $st$ represents the shortest path from vertex $s$ to vertex $t$. The notation $|st|$ denotes the length of this path (same as the number of edges in the $st$ path for unweighted graphs). The notation $st \DIA F$ denotes the shortest path from $s$ to $t$ while avoiding a set of edges $F=\{e_1,e_2\}$, and $|st \DIA F|$ corresponds to the length of that path.

§.§ Overview of the approach in <cit.>

Suppose we want to find the path $P= st \DIA F$. In <cit.>, the authors introduced the concept of `maximiser', which will be discussed further in later sections. For now, we want to emphasize on the fact that the `maximisers' output either the length of the path $P$ or a set of vertices serving as a `hitting set' of $P$. We will formally prove this later. Together with these  `maximisers', they also used a structural theorem of shortest paths under edge failures to use the hitting set effectively. A path is said to be $f$-decomposable if it is the concatenation of at most $(f + 1)$ shortest paths in $G$.
In <cit.>, the authors show the following:

(Theorem 1 in <cit.>) For  any set of failures $F$ of size $f$, every shortest path from $s$ to $t$ avoiding $F$ is $f$-decomposable.

Let us now discuss an important aspect of this theorem. Let $P = st \DIA \{e_1,e_2\}$ be 2-decomposable and $x$ be a vertex of the hitting set which lies on the path $P$. Since $P$ is 2-decomposable, it contains at most three shortest paths, say $A$, $B$, and $C$, where $P$ starts with the path $A$ and ends with the path $C$. If $x$ lies on $B$, then $P[s,x]$ and $P[x,t]$ are 1-decomposable. Thus, we have hit path $P$ and reduced the problem into two smaller subproblems (in terms of decomposability). However, if $x$ lies on $A$ or $C$, then we have not reduced the problem. The whole game now is to design an algorithm that can find an $x \in B$. In <cit.>, Ren and Duan design such an algorithm. Since our strategy is similar, let us define some notations that formalise our discussion.

(First and the last segment in a path and an intermediate vertex)

Let us assume that $F$ is a set of size $f$ and $P=st \DIA F$ is $f$-decomposable. Thus, $P$ can be decomposed into at most $f+1$ shortest paths. Let $A$ and $B$ be the first and the last shortest path from these $ f+1$ shortest paths. Thus, $A$ is the shortest path that starts from $s$, and $B$ is the shortest path that ends at $t$. $A$ is called  the first segment of the path $P$ and $B$ is called the last segment of the path $P$.  If a vertex $x \in P$ does not lie in the first and last segments, then it is called an intermediate vertex.

Before we describe further, let us at first define some notations.

A path $sx$ is said to be intact from failures $\{e_1,e_2\}$ if the endpoints of $e_1$ and $e_2$ do not lie strictly between[<cit.> did not require the endpoints to be strictly inside. However, we require it to avoid some corner cases.] $s$ and $x$ on the path $sx$. Similarly, if the subtree under a node $x$ in $T_s$, that is $T_s(x)$, do not contain any endpoints of $e_1$ and $e_2$, it is intact from failures $\{e_1,e_2\}$.

The above definition may appear natural. However, it is not. Usually, when we say that a path or tree is intact from failures $\{e_1,e_2\}$, we mean that it does not contain $e_1$ and $e_2$. In contrast, the above definition does not allow the endpoints of $e_1$ and $e_2$. Though never emphasised, this fact is used crucially in the algorithm of Ren and Duan <cit.>.
We now define the notion of a clean vertex introduced in <cit.>.

A vertex $x$ is called $s$-clean from $\{e_1,e_2\}$ if $sx$ and $T_s(x)$ are intact from failures $\{e_1,e_2\}$.

Duan and Ren used the above `clean' vertices crucially in <cit.>. Let \(P = st\DIA F\) be \(f\)-decomposable. As mentioned above, we want to find an intermediate vertex \(x\) on \(P\), after which we can recurse on \(P[s,x]\) and \(P[x,t]\). To this end, <cit.> designed an algorithm $\QU$, which is initially called using the parameters \((s,t, F,f)\). The main component of this algorithm is the function \(\textsc{HitSet}\), a function that uses maximisers. HitSet outputs \(O(\text{poly}(f))\) edges \(H\) and an upper bound on $|P|$, which is stored in \(L\). The function \(\textsc{HitSet}\) has the following properties: (1) Either \(L = |P|\) or (2) One of the endpoints of the edges in \(H\) hits \(P\) and is an intermediate vertex.
Thus, we either find our answer or recurse on two parts in Line 6 of Algorithm 1. One can check that if the running time of HitSet is polynomial in \(f\), then the running time of the query algorithm is \(O(f^{O(f)})\). In our case, this is \(O(1)\) since \(f = 2\).

Query Algorithm for the Exact Distance Oracle: Query$(s,t,F, f)$

if $st \cap \{e_1,e_2\} = \emptyset$ return $|st|$

if $f=0$ return $\infty$

$(L, H) \leftarrow \textsc{HitSet}(s, t, F)$

$\AN \leftarrow L$
each $x$ in $H$
$\AN \leftarrow \min\{\text{ans}, \textsc{Query}(s, x, F, f-1) + \textsc{Query}(x, t, F, f-1)\}$;

We now give an overview of how to find an intermediate vertex. Let us assume the worst case when the output of our maximisers always hit the path \(P\). The key to finding an intermediate vertex is first finding a clean vertex from the source and the destination, i.e., an \(s\)-clean and \(t\)-clean vertex. The authors first show how to design an appropriate maximiser that ensures we obtain a clean vertex. Once a \(s\)-clean and \(t\)-clean vertex are found, authors design an appropriate maximiser that gives us an intermediate vertex. This approach is succinctly described in the <Ref>. This figure illustrates behaviour of the HitSet algorithm in the worst case. In the best case, the first call to the maximiser may give us an intermediate vertex.

Though we have hidden many technical details, we want the reader to note the steps required to find an intermediate vertex in the worst case. Also, to use their maximisers, they needed $O(n^4)$ space which we reduced in this paper for $2$ faults.

§.§ Overview of our approach

We define some new notations which will help us in describing our approach. Suppose we want to find $st \diamond F$ where $F=\{e_1,e_2\}$.

(Primary and Secondary path)

The shortest $st$ path is referred to as the primary path, which includes the edge $e_1$. The secondary path is $st \DIA e_1$.

Following the above definition, we assume that the primary path contains $e_1$ (without loss of any generality). If the primary path contains none of the edges $e_1$ and $e_2$, then finding $st \DIA \{e_1,e_2\}$ is trivial. If the primary and the secondary path do not contain $e_2$, then we can use the single edge fault-tolerant data structure of Demestrescu et al. <cit.> to find $|st \DIA e_1|$. This is also an easy case. For the rest of the paper, we will assume that we are in one of the two cases:

* $e_1$ and $e_2$ both lie on the primary path

* $e_1$ lies on the primary path and $e_2$ lies on the secondary path.

To apply our algorithm, we should quickly identify in which case we are operating. For this, we will introduce small weights to our originally unweighted graph similar to <cit.>. This will ensure unique shortest paths between any two vertices in the graph, even after the occurrence of two faults. Let us abuse notation and use  $|st|$ as the weight of the shortest path in this weighted graph. Also, let us define $w(e)$ as the weight of edge $e$ in this new graph. To find if $e_1 $ lies on the $st$ path, we just need to check if $|st| = |se_1| + w(e_1) + |e_1t|$. Note that we can fetch these quantities in $O(1)$ time if we have stored the shortest path tree from each vertex in the graph. So, we can check if both $e_1$ and $e_2$ lie on the $st$ path in $O(1)$ time. Similarly, we can find if $e_2$ is in secondary path  by checking is $|st \DIA e_1| = |se_2 \DIA e_1| + w(e_2) +\ |e_2t\DIA e_1|$.  Again, all the quantities can be found in $O(1)$ time using the one fault data structure of <cit.>. Henceforth, we will assume that we know the case in which we are operating.

We will show later that case (1) (both faults lie on the primary path) is similar to one of the subcases of the case (2) ($e_1$ on the primary path and $e_2$ on the secondary path). The bulk of our paper will be devoted to case (2). Henceforth, we will always assume the following setting: we want to find the shortest path from $s$ to $t$ avoiding $e_1=(a,b)$ and $e_2=(c,d)$. We will assume that $e_1 \in st$ and $e_2 \in st\DIA e_1$ where $a$ and $c$ are near to $s$ on $st$ and $st \DIA e_1$ paths respectively (See <Ref>).
Let $P = st\DIA \{e_1,e_2\}$ be a 2-decomposable path. We now define the notion of the detour of the path $P$.

(Detour of a path $P$, start and end of a detour)

The detour of the path $P$ is $P \setminus (st \cup st \DIA e_1)$.
The start of the detour is the first vertex on $P$, after which $P$ deviates from $st \cup st \DIA e_1$. If this vertex is on $st$, then we say that the detour starts on the primary path. If it is on $st \DIA e_1 \setminus st$, then we say that it starts on the secondary path. Similarly, we can define the end of the detour.

Note that the above definition of detour differs slightly from what is usually used in literature. Specifically, the start of the detour is generally defined as the vertex on the path $P$, after which $P$ deviates from $st$. In our definition, the detour can start on the primary path or the secondary path. Similarly, the detour may end on the primary or the secondary path.

Before we describe our main technical contribution, we redefine the notion of the "intact from faults" and a "clean vertex" is slightly different from <cit.>.

A path $sx$ is considered intact from failures   $F$ if no edges of $F$ lie on it. Similarly, the subtree under a node $x$ in $T_s$, that is, $T_s(x)$, is intact from failures $F$ if no edges of $F$ lie in $T_s(x)$. The vertex $x$ is called $s$-clean from $F$ if $sx$ and $T_s(x)$ is intact from  failures $F$.

Note the difference between our notion of intact from failures with that of <cit.>.

In this paper, we use an approach similar to that used in <cit.>. Essentially, our objective is to identify vertices along the path $P = st \DIA \{e_1, e_2\}$ that are `close to the detour' from the vertices $s$ and $t$. Before describing what we exactly mean by `close to the detour', let us define a suitable set of vertices called landmark vertices. These landmark vertices play a crucial role in the forthcoming definitions.

(Landmark vertices)

Let $\LL_i$ be the set of vertices sampled from $V$ with a probability of $\frac{c\log n}{2^i}$, where $0 \leq i \leq \log n$ and $c>1$ is a constant. The size of $\LL_i$ is $\TL\left(\frac{n}{2^i}\right)$ with a probability $\ge (1-\frac{1}{n^c})$.

We are now ready to describe our main contribution in this paper via the following two definitions:

( Close vertex to a faulty edge from $s$)

Let $P = st \DIA \{e_1,e_2\}$. A vertex $x \in P$ is called close vertex  to edge  $e_1$  from $s$ if $x \in \LL_{\EL}$ (for some $\EL \in [0, \log n]$), $sx$ avoids $\{e_1,e_2\}$ and $|xe_1 \DIA \{e_1,e_2\}| = O(2^{\EL})$. The definition is similar for close vertex to $e_2$. Similarly, we can define close vertex to a faulty edge from $t$.

In most parts of the paper, we will find a close vertex from $s$. So, for brevity, we will drop the term "from $s$" where it is clear from the context that we are finding a close vertex from $s$. We aim to find a close vertex with one more special property. Next, we define the detour close vertex or D-close vertex. This will be close to faulty edge $e_1$ or $e_2$ depending on where the detour starts.

(A detour close or D-close vertex to a faulty edge from $s$)

Let $P = st \DIA \{e_1,e_2\}$. Let us assume that the detour of $P$ starts on the primary path.
A vertex $x \in P$ is called D-close to $e_1$ if $x$ is close to $e_1$ and the detour of $P$ starts in $xe_1 \DIA \{e_1,e_2\}$ path ($xe_1 \DIA \{e_1,e_2\}$ represents the path from $x$ to $e_1$ on the primary path). If the detour of $P$ starts on the secondary path, the definition of D-close to $e_2$ is similar (with $xe_1\DIA \{e_1,e_2\}$ replace by $xe_2 \DIA \{e_1,e_2\}$, which represents the path from $x$ to $e_2$ on the secondary path). Similarly, we can define a $D$-close vertex from $t$.

Our central intuition is that once we have found a $D$-close vertex from $s$ and $t$, we can use  Ren and Duan's approach to find an $s$-clean or $t$-clean vertex. Note that finding a $D$-close vertex is not the main aim. The aim is to find an intermediate vertex. If we find a clean or intermediate vertex at any point in our algorithm, we abandon our search for a $D$-close vertex as our job is already done. We now design our version of HitSet algorithm in the <Ref>.  In <Ref>, we show behaviour of our HitSet algorithm in the worst case: the first call may give us a $D$-close vertex from $s$. The second call gives us a $D$-close vertex from $t$. After that, we will find either an $s$-clean vertex or a $t$-clean vertex, and the remaining figure is same as <Ref>.

In essence, our result implies we should first find a vertex on $P$ that is  $D$-close to the fault. Similar kind of strategy can be found in <cit.>. This strategy not only decreases the query time but also improves the space taken by the algorithm. Finding a  $D$-close vertex is easy when there is one fault. In our paper, we show how to find a $D$-close vertex (using maximisers) when there are two faults.
Unfortunately, we will not be able to use the maximisers of Ren and Duan<cit.> as its size is $O(n^4)$. We will design new maximisers different from <cit.>, taking just $\TL(n^2)$ space. In fact, all the maximisers used in our  $\HIT$ algorithm take $\TL(n^2)$ space.
This completes the description of our overview.

§ PRELIMINARIES

Till now, we have discussed about the shortest path and shortest distance between any two vertices. In our paper, we also use notion of the shortest distance between a vertex and an edge. For an edge $e = (u,v)$ and a vertex $s$, $|se|$ is defined as the minimum of $|su|$ and $|sv|$.  Also, $|se \DIA F| = \min\{|su \DIA F|, |sv \DIA F| \}$.  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 the length of this subpath. Also, $V(e)$ denotes the set containing both the endpoints of $e$, i.e., $V(e) = \{u,v\}$. $T_s$ denotes the shortest path tree rooted at $s$. For any vertex $x$ in $T_s$, $T_s(x)$ represents the subtree rooted at node $x$ in $T_s$. In our algorithm, we may need to quickly find the least common ancestor () of any pair of vertices $u$ and $v$ in $T_s$. We will utilise the following result to find the LCA efficiently:

(See <cit.> and its references) Given a tree $T$ with $n$ vertices, we can construct a data structure of size $O(n)$ in $O(n)$ time, allowing us to answer LCA queries in $O(1)$ time.

We will use the following lemma to show the existence of landmark vertex (defined in <Ref>) with high probability on sufficiently long paths. We state this lemma without proof.

Let $U_i$ be the set of paths such that length of each path is $\Omega(2^i)$. If size of $U_i$ is poly($n$), then with a probability $\ge 1-1/n$, for all $0 \le i \le \log n$ and for each path $P \in U_i$, there exists a vertex in $\LL_i$ that hits $P$.

We use another concept from the works of <cit.> which is named as  trapezoid of a path or the near vertices of a path. Before that, let us describe another notion below:

(Ball from a vertex of length $\EL$, $\BA_G(u,\EL)$ )

A ball from a vertex $u$ of length $\EL$ is a set containing all the vertices at distance $\le \EL$ from $u$. We denote this ball by $\BA_G(u,\EL)$. Formally, $\BA_G(u,\EL) = \{v \ |\ |uv| \leq \EL \}$.

Let $P=st \DIA F$. Let us now define trapezoid of that path.

(Trapezoid of $P$ in $G \setminus F$, $\TR_{G \setminus F}(P)$)

Let $P$ be an arbitrary path from $s$ to $t$ in $G \setminus F$. Define the trapezoid of $P$ in $G \setminus F$ as:

$$\TR_{G \setminus F}(P)=\Big(\bigcup_{u \in P \setminus \{s,t\}} \BA_{G/F}(u, \epsilon \min\{|P[s,u]|,|P[u,t]|\})\Big)\setminus \{s,t\}$$

where $\EP \ge 0$ is a parameter. In words, for each vertex $u \in P$, we include all vertices that are in the ball of length $\EP \EL_u$ in $G \setminus F$ where $ \EL_u$ is the minimum of the length of $u$ from $s$ and $t$ on path $P$. All these vertices lie in the trapezoid of $P$. A vertex is  far away  from $P$ if it does not lie in the trapezoid of $P$.

Chechik et al.<cit.> introduced the notion of the trapezoid and designed a data structure $\FT$. Though we will not use the $\FT$ data structure in our paper, we will crucially use the notion of a trapezoid.
In <cit.>, the authors introduced a technique called the maximiser for a pair of vertices $s$ and $t$.

\begin{equation}
\label{eq:1}
\DD(s,t, x,y, b_1, b_2) = \text{argmax}_{F \in E^2}\left\{ \text{conditions depending on $s$, $t$, $x$, $y$, $b_1$ and $b_2$ }\right\}
\end{equation}

In the above maximiser, $s$ is the source, and $t$ is the destination. Variables $x$ and $y$ can be any two arbitrary vertices. The boolean variables $b_1, b_2$ gave some extra conditions on the pair of faults they are considering. Let $e_1^*$ and $e_2^*$ be the edges returned (or stored) by the above maximiser. Note that we can also store the path length $|st \DIA \{e_1^*,e_2^*\}|$ without increasing the size.

We first describe the power of these maximisers. Let us assume that we want to find the shortest path from $s$ to $t$ avoiding  $\{e_1,e_2\}$. If $\{e_1,e_2\}$ satisfy the conditions of the maximiser $\DD$, then we can show that edges returned by the maximiser $\DD$ hit the path $st \DIA \{e_1,e_2\}$ or we have got the length of the path $st \DIA \{e_1,e_2\}$.

Let $P=st \diamond \{e_1,e_2\}$ and $\DD(s,t,x,y) = \{e_1^*,e_2^*\}$.  If $\{e_1,e_2\}$ satisfies conditions of $\DD$, then  either $e_1^*$ or $e_2^*$  lie on $P$ or $|P|=|st \DIA \{e_1^*,e_2^*\}|$.

Let us assume that neither $e_1^*$ nor $e_2^*$ lies on $P$.
Since $\{e_1,e_2\}$ also satisfies the condition given in $\DD$,  $|P| \leq |st \DIA \{e_1^*,e_2^*\}|$.

Since $P$ also avoids $e_1^*$ and $e_2^*$,  $|st \DIA \{e_1^*,e_2^*\}| \leq |P|$. This implies $|P| = |st \DIA \{e_1^*,e_2^*\}|$.

Using the above lemma, either we find the length of the path $st \DIA \{e_1,e_2\}$ or we get a very small set that hits $P$. We now formally describe the maximisers created in <cit.> and how they use the notions of $s$-clean and $t$-clean vertices. Let $bits$ be an array of size 2 (we replace $b_1,b_2$ used by them by $bits$ for our presentation). Each cell in bits can either be 0 or 1. We will now define four maximisers $\DD_{bits}(s,t,x,y)$ depending on the value in $bits$. The conditions of the maximisers are as follows:(1) $sx$ and $ty$ are intact from faults and (2)  If $bits[0] = 1$, then  $x$ is $s$-clean. Similarly, if $bits[1]=1$, then  $y$ is $t$-clean. We give the complete definition of one of the maximisers, $\DD_{01}(s,t, x,y) = \text{argmax}_{\{e_1^*,e_2^*\} \in E^2}\left\{ \text{$sx$ is intact from  faults $\{e_1^*,e_2^*$\} and $y$ is $t$-clean from $\{e_1^*,e_2^*\}$ } \right\}$.

In the above definition, $s,t,x,y \in V$. Thus, the total size of $\DD_{01}$ is $O(n^4)$. It is easy to observe that all the other three maximisers will also be of size $O(n^4)$.  We have already discussed in <Ref> about how these maximisers are used. In this paper, we have modified these maximisers to have an oracle with size $\TL(n^2)$.