Fault-Tolerant Approximate Distance Oracles with a Source Set

The first fault-tolerant exact distance oracle was designed by Demetrescu and Thorup in 2002 [14] and it was for directed weighted graphs. Their oracle handles single edge failures and has size $O(n^2\log n)$ with $O(1)$ query time. After this result, there has been a long line of research on the problem of efficiently constructing single edge/vertex fault-tolerant exact distance oracles. Ignoring preprocessing time, the most space-efficient oracle is by Duan and Zhang [19] with size $O(n^2)$ and query time $O(1)$. Thus it shaves off the $\log n$ factor from the size of the original oracle.

Fault-tolerant sourcewise distance oracles. For undirected unweighted graphs, Gupta and Singh [20] designed a single edge fault-tolerant sourcewise exact distance oracle of size $\tilde{O}(n^{3/2}\sqrt{|S|})$ with $\tilde{O}(1)$ query time and source set $S$. In undirected graphs with edge weights in the range $\{1,2,\mathrm{\dots },M\}$, Bilò, Cohen, Friedrich and Schirneck [10] designed a fault-tolerant single source exact distance oracle. This oracle handles single edge failures and has size $\tilde{O}(n^{3/2}\sqrt{M})$ with query time $\tilde{O}(1)$. For undirected unweighted graphs, Dey and Gupta [15] designed a different oracle with the same space and query time bounds as in [10], but with a faster preprocessing time.

$ST$-distance oracles in directed graphs. In directed weighted graphs, Bilò, Choudhary, Gualà, Leucci, Parter and Proietti [9] designed a fault-tolerant $ST$-distance oracle, i.e., it maintains exact distances for all pairs in $S\times T$, for given vertex subsets $S$ and $T$. It handles single edge failures and has size $\tilde{O}((|S|+|T|)n)$ with $O(1)$ query time, where $n$ is the number of vertices. They also designed a fault-tolerant $ST$-distance oracle in unweighted directed graphs of size $\tilde{O}(n\sqrt{|S||T|})$ with query time $O(\sqrt{|S||T|})$. Furthermore, they showed a fault-tolerant $ST$-approximate distance oracle in directed unweighted graphs that returns in constant time a distance estimate stretched by an additive term. In particular, when $|S|=O(\sqrt{n})$, their oracle has size $\tilde{O}(n^{3/2})$ and additive stretch $\tilde{O}(\sqrt{n})$.

Approximate distance oracles that provide distances within a small multiplicative stretch for all vertex pairs have been extensively studied. Table 1 summarizes results for fault-tolerant approximate distance oracles in directed/undirected graphs. Note that the stretch here is multiplicative, except for the last row where the stretch has an additive term as well.

For single edge faults, note that Chechik, Langberg, Peleg, and Roditty [13] showed an approximate distance oracle with stretch 12 and size $\tilde{O}(n^{3/2})$ and another with stretch 28 and size $\tilde{O}(n^{4/3})$. In comparison to this, Theorem 1 shows a sourcewise approximate distance oracle with stretch 5 and size $\tilde{O}(|S|n+n^{3/2})$ and Theorem 2 shows a sourcewise approximate distance oracle with stretch 13 and size $\tilde{O}(|S|n+n^{4/3})$. Thus for small sets $S$, our oracles are as sparse and have smaller stretch. Note that for single faults and every $k\ge 1$, approximate distance oracles by Baswana and Khanna [2] are almost as sparse as the oracles in [13] and have significantly smaller stretch. However these oracles work only for unweighted graphs.

It is an open problem if our construction can be generalized to work for all integers $k$, in other words, to show a sourcewise approximate distance oracle of size $\tilde{O}(|S|n+n^{1+1/k})$ and stretch $8k-3$ with $O(1)$ query answering time for $k\ge 3$. Our results show such a construction for $k=1,2$. Note that the remaining approximate distance oracles in Table 1 have superconstant query time, so our oracles cannot directly be compared with them.

Our algorithms are simple to describe and use the $ST$-distance oracle by Bilò, Choudhary, Gualà, Leucci, Parter and Proietti [9]. Their oracle uses landmark vertices, i.e., vertices picked uniformly at random from the vertex set $V$ (originally used by Bernstein and Karger [4]).²²2To the best of our knowledge, the name “landmark” vertices was first used by Dey and Gupta [16]. The oracle in Theorem 1 uses this $ST$-distance oracle for the given source set $S$ and $T=S\cup ℒ$, where $ℒ$ is our landmark vertex set. The oracle in Theorem 2 is based on the same idea, however there are two levels of sampling here: so we have two landmark vertex sets ${ℒ}_2\subseteq {ℒ}_1$. Theorem 1 and Theorem 2 are proved in Section 3 and Section 4, respectively. We discuss preliminaries in Section 2 and conclude in Section 5.

Since each vertex in $G$ is sampled independently with probability $p$, for any pair of vertices $u$ and $v$, the probability that there is no landmark vertex on $uv$ is ${(1-p)}^k$ where $k=|uv|+1$ is the number of vertices on $uv$. Because $|uv|\ge \lfloor \frac{3\ln n}{p}\rfloor$, the probability that there is no landmark vertex on $uv$ is at most:

Thus for any pair of vertices $u$ and $v$ with $|uv|\ge \lfloor \frac{3\ln n}{p}\rfloor$, the probability that there is no landmark vertex on $uv$ is at most $1/n^3$. Hence the probability that there is some pair $(x,y)\in V\times V$ with $|xy|\ge \lfloor \frac{3\ln n}{p}\rfloor$ such that there is no landmark vertex on $xy$ is at most $\left(\genfrac{}{}{0pt}{}{n}{2}\right)/n^3\le 1/n$. Thus with probability at least $1-1/n$, it is the case that for every pair $(u,v)\in V\times V$ with $|uv|\ge \lfloor \frac{3\ln n}{p}\rfloor$, there is at least one landmark vertex on $uv$. $◀$

Since each vertex in $G$ is sampled with probability $p$, the expected size of $ℒ$ is $np$. We will set $p=n^{-\delta }$ for some $\delta \in (0,1)$ in Section 3 and Section 4. Thus with high probability, we will have $|ℒ|\le 2np$ (by Chernoff bound).

• $\mathrm{■}$

  If either $|ℒ|>2np$ or there exists a pair of vertices $u,v$ with $|uv|\ge \lfloor \frac{3\ln n}{p}\rfloor$ such that there is no vertex of $ℒ$ on $uv$ then we will repeat the step of sampling vertices and construct another landmark vertex set such that both these properties hold for the set obtained.

Thus we will assume that $|ℒ|=O(np)$ and every pair of vertices $u,v$ with $|uv|\ge \lfloor \frac{3\ln n}{p}\rfloor$ has at least one vertex of $ℒ$ on $uv$. The expected number of trials to obtain a desired landmark set $ℒ$ is $O(1)$.

We now briefly discuss the algorithm of Bilò et al.[9] to construct a fault-tolerant exact distance oracle in $G$ for pairs $(s,t)\in S\times T$, where $S\subseteq V$ and $T\subseteq V$ are part of the input. Fix a pair $(s,t)\in S\times T$ and let $f=(a,b)$ be any edge on $st$. Let $\mathrm{\ell }$ and ${\mathrm{\ell }}^{\prime }$ be the two landmark vertices on $st$ closest to $a$ and $b$ on $as$ and $bt$, respectively.

There are 3 cases with respect to the replacement path $st\diamond f$: (i) $st\diamond f$ goes through $\mathrm{\ell }$, (ii) $st\diamond f$ goes through ${\mathrm{\ell }}^{\prime }$, (iii) $st\diamond f$ goes through neither $\mathrm{\ell }$ nor ${\mathrm{\ell }}^{\prime }$. Their algorithm builds tables to deal with each of these cases. Figure 1 captures the main idea.

The following theorem from [9] will be used in our algorithms.

Recall Definition 3 on landmark vertices. Let us sample each vertex independently with probability $p=(3\ln n)/\sqrt{n}$ to obtain our landmark vertex set $ℒ$. The following two properties hold (see Proposition 4); otherwise we resample to obtain another landmark vertex set $ℒ$ so that the following two properties hold.

• $\mathrm{■}$

  $|ℒ|=O(\sqrt{n}\log n)$.

• $\mathrm{■}$

  For any pair of vertices $u$ and $v$: if $|uv|\ge \lfloor \sqrt{n}\rfloor$, then there is at least one landmark vertex on $uv$.

On input $G=(V,E)$ and $S\subseteq V$, the first step of our algorithm is to build the above landmark vertex set $ℒ$. We then compute shortest path trees $𝒯(u)$ rooted at $u$ for all $u\in S\cup ℒ$. Along with every vertex $v$, the tree $𝒯(u)$ also has the two attributes $\Vert uv\Vert$ and $|uv|$, i.e., the length and the hop length of $uv$.

Our algorithm constructs the $ST$-exact distance oracle from [9] fixing the source set $S$ and destination set $T=S\cup ℒ$. For each $v\in V$, let $t_v$ be the vertex in $T$ that is closest to $v$, where ties are broken arbitrarily. We maintain the lengths of replacement paths $v{t}_v\diamond f$ for each edge $f\in v{t}_v$. Our algorithm is described below.

1. 1.

   Obtain the landmark vertex set $ℒ$.

2. 2.

   For each $u\in S\cup ℒ$ do: compute the shortest path tree $𝒯(u)$ rooted at $u$ in $G=(V,E)$.

3. 3.

   Use Theorem 5 to construct an $ST$-exact distance oracle for the given source set $S$ and target set $T=ℒ\cup S$ in $G=(V,E)$.

4. 4.

   For every $v\in V$ in the graph $G=(V,E)$ do:

   • $\mathrm{■}$

     Identify the nearest vertex to $v$ in the target set $T=ℒ\cup S$. Call this vertex $t_v$.

   • $\mathrm{■}$

     For $1\le i\le |v{t}_v|$ do:

     • –

       Let $f_i$ be the $i$-th edge from $t_v$ on $v{t}_v$.

     • –

       Compute the distance $\Vert v{t}_v\diamond f_i\Vert$ between $v$ and $t_v$ in $G-f_i$.

     • –

       Set ${\mathrm{𝖣𝗂𝗌𝗍}}_T[v,i]=\Vert v{t}_v\diamond f_i\Vert$.

In response to the query $Qu(s,v,f)$, the query answering algorithm first checks if $f\in sv$. This check can be done efficiently via LCA queries. Given a rooted tree $𝒯$ and a pair of vertices $x,y$ in the tree $𝒯$, recall that ${\mathrm{𝖫𝖢𝖠}}_{𝒯}(x,y)$ is the least common ancestor of $x$ and $y$ in tree $𝒯$.

Observe that $f=(a,b)\in sv$ if and only if the answer to the following three questions is “yes” where $𝒯(s)$ is the shortest path tree in $G$ rooted at $s$.

• $\mathrm{■}$

  Is ${\mathrm{𝖫𝖢𝖠}}_{𝒯(s)}(v,a)$ equal to $a$?

• $\mathrm{■}$

  Is ${\mathrm{𝖫𝖢𝖠}}_{𝒯(s)}(v,b)$ equal to $b$?

• $\mathrm{■}$

  Is $|sa|+1=|sb|$ or is $|sb|+1=|sa|$?

A “yes” answer to the first two questions implies that both $a$ and $b$ are vertices on the path $sv$. Moreover, $a$ and $b$ are adjacent to each other on $sv$ if and only if the answer to the third question is “yes”. Recall that for any vertex $w$, $|sw|$ is the hop length between $s$ and $w$, i.e., the number of edges in $sw$.

Given a tree $𝒯$, there is a linear time algorithm to build an $O(n)$ size data structure such that LCA queries on $𝒯$ can be answered in $O(1)$ time [3]. Recall that for every vertex $w$, the hop length $|sw|$ is stored along with $w$ in $𝒯(s)$. Thus $|sa|$ and $|sb|$ can be retrieved in $O(1)$ time. Hence the query answering algorithm can determine in $O(1)$ time if $f\in sv$ or not. The query answering algorithm will return $\Vert sv\Vert$ if $f\notin sv$ (see Figure 2). Recall that the distance $\Vert sv\Vert$ is also stored along with $v$ in $𝒯(s)$.

If $f\in sv$, then the query answering algorithm looks up the identity of $t_v$, which is the nearest vertex in $T$ to $v$. Via LCA queries on $𝒯(t_v)$, we can determine if $f=(a,b)\in v{t}_v$ or not. If not, then $\Vert v{t}_v\diamond f\Vert =\Vert v{t}_v\Vert$. So let us assume $f\in v{t}_v$.

Assume without loss of generality that $b$ is closer than $a$ to $t_v$, i.e., $|a{t}_v|=|b{t}_v|+1$ (see Figure 2). Let $i$ be the index such that $a$ is the $i$-th vertex from $t_v$ on $v{t}_v$. Then $\Vert v{t}_v\diamond (a,b)\Vert ={\mathrm{𝖣𝗂𝗌𝗍}}_T[v,i]$. Recall that the attribute $i=|a{t}_v|$ is stored along with $a$ in $𝒯(t_v)$.

• $\mathrm{■}$

  The query answering algorithm returns $\Vert v{t}_v\diamond f\Vert +\Vert s{t}_v\diamond f\Vert$, where $\Vert v{t}_v\diamond f\Vert ={\mathrm{𝖣𝗂𝗌𝗍}}_T[v,i]$.

Note that the distance $\Vert s{t}_v\diamond f\Vert$ is obtained by querying the $ST$-distance oracle. Thus the query answering time is $O(1)$. We show below that $\Vert v{t}_v\diamond f\Vert +\Vert s{t}_v\diamond f\Vert \le 5\Vert sv\diamond f\Vert$.

It follows from the discussion above that the query answering time is $O(1)$. Since the query answering algorithm will return $\Vert sv\Vert$ if $f\notin sv$ (see Figure 2), let us assume $f\in sv$. Then the distance estimate returned by the query answering algorithm in response to query $Qu(s,v,f)$ is $\Vert s{t}_v\diamond f\Vert +\Vert v{t}_v\diamond f\Vert$ where $t_v$ is the nearest vertex in $T$ to $v$. We now bound the sum $\Vert s{t}_v\diamond f\Vert +\Vert v{t}_v\diamond f\Vert$. Consider the following four cases.

1. 1.

   $f\in s{t}_v$ and $f\in v{t}_v$. This means the edge $f$ belongs to the shortest path between $t_v$ and the least common ancestor of $s$ and $v$ in $𝒯(t_v)$ (see Figure 2). However then $f\notin sv$, contradicting our assumption that $f\in sv$.

2. 2.

   $f\in s{t}_v$ and $f\notin v{t}_v$. The query answering algorithm will determine via LCA queries that $f\notin v{t}_v$, so $\Vert v{t}_v\diamond f\Vert =\Vert v{t}_v\Vert$. Let us bound $\Vert s{t}_v\diamond f\Vert$. The graph $G-f$ has an $s$-$t_v$ path obtained by stitching the paths $sv\diamond f$ and $v{t}_v$, i.e., the path $sv\diamond f$ followed by $v{t}_v$. So $\Vert s{t}_v\diamond f\Vert \le \Vert sv\diamond f\Vert +\Vert v{t}_v\Vert$. Hence the distance returned is at most $\Vert sv\diamond f\Vert +2\Vert v{t}_v\Vert$.

   • $\mathrm{■}$

     Because $t_v$ is the closest vertex in $T=ℒ\cup S$ to $v$, we have $\Vert v{t}_v\Vert \le \Vert vs\Vert$. Hence the distance returned is at most $\Vert sv\diamond f\Vert +2\Vert sv\Vert \le 3\Vert sv\diamond f\Vert$. So the stretch is at most 3 in this case.

3. 3.

   $f\notin s{t}_v$ and $f\in v{t}_v$. Since $f\notin s{t}_v$, we have $\Vert s{t}_v\diamond f\Vert =\Vert s{t}_v\Vert$. Let us bound $\Vert v{t}_v\diamond f\Vert$. Since the graph $G-f$ has a $v{t}_v$ path obtained by stitching $sv\diamond f$ and $s{t}_v$, we have $\Vert v{t}_v\diamond f\Vert \le \Vert sv\diamond f\Vert +\Vert s{t}_v\Vert$ (see Figure 3). Thus the distance returned by the oracle is at most $\Vert sv\diamond f\Vert +2\Vert s{t}_v\Vert$.

   • $\mathrm{■}$

     Observe that $\Vert s{t}_v\Vert \le \Vert sv\Vert +\Vert v{t}_v\Vert \le 2\Vert sv\Vert$. Hence the distance returned is at most $\Vert sv\diamond f\Vert +4\Vert sv\Vert \le 5\Vert sv\diamond f\Vert$. Thus the stretch is at most 5 in this case.

4. 4.

   $f\notin s{t}_v$ and $f\notin v{t}_v$. The query answering algorithm will return $\Vert s{t}_v\diamond f\Vert +\Vert v{t}_v\diamond f\Vert =\Vert s{t}_v\Vert +\Vert v{t}_v\Vert$ in this case. We have $\Vert v{t}_v\Vert \le \Vert vs\Vert$ and we also have $\Vert s{t}_v\Vert \le \Vert sv\Vert +\Vert v{t}_v\Vert \le 2\Vert sv\Vert$. Thus the stretch is at most 3 in this case.

This finishes the proof of the lemma. $◀$

Our algorithm constructs in step 3 all the data structures constructed by the $ST$-distance oracle algorithm. Thus we have access to $\Vert st\diamond f\Vert$ for every $(s,t)\in S\times T$ and $f\in E$. Our oracle also has the table ${\mathrm{𝖣𝗂𝗌𝗍}}_T$ that stores $\Vert v{t}_v\diamond f\Vert$ between $v$ and $t_v$ in $G-f$, for each $v\in V$ and edge $f\in v{t}_v$. Let us bound the size of our oracle.

The size of $T$ is $\tilde{O}(|S|+\sqrt{n})$. So the sizes of all the shortest path trees constructed in step 2 is $\tilde{O}(|S|n+n^{3/2})$. Similarly, the size of the $ST$-oracle constructed in step 2 is $\tilde{O}(|S|n+n^{3/2})$ (by Theorem 5). Furthermore, the data structure used to answer LCA queries on each shortest path tree $𝒯(u)$ has size $O(n)$. Since $u\in S\cup ℒ$, these data structures also take up space $\tilde{O}(|S|n+n^{3/2})$.

It follows from the property of our landmark set $ℒ$ that for any vertex $v$, we have $\min \{|v\mathrm{\ell }|:\mathrm{\ell }\in ℒ\}\le \lfloor \sqrt{n}\rfloor$. So for each vertex $v$, we have $\Vert v{t}_v\diamond f\Vert$ stored for at most $\lfloor \sqrt{n}\rfloor$ many edges $f$, where $t_v$ is the nearest vertex in $T$ to $v$. Thus the size of ${\mathrm{𝖣𝗂𝗌𝗍}}_T$ is $O(n\cdot \sqrt{n})=O(n^{3/2})$. This finishes the proof of the lemma. $◀$

It is easy to see that our algorithm runs in expected polynomial time. Recall that we used randomization to construct the set $ℒ$. By blowing up the size of $ℒ$ by a factor of $\log n$, the construction of $ℒ$ can be made deterministic (see [9, Lemma 1]). Thus Theorem 1 follows. We restate it below for convenience. See 1

We will now construct two sets ${ℒ}_1$ and ${ℒ}_2$ of landmark vertices. We will first run the sampling step in Section 2 with $p=(3\ln n)/n^{1/3}$. Let ${ℒ}_1$ be the resulting landmark set. The following properties follow from Section 2 (see Proposition 4).

• $\mathrm{■}$

  $|{ℒ}_1|=O(n^{2/3}\log n)$.

• $\mathrm{■}$

  For any pair of vertices $u$ and $v$: if $|uv|\ge \lfloor n^{1/3}\rfloor$ then there is at least one vertex of ${ℒ}_1$ on $uv$.

After that, we sample each vertex of ${ℒ}_1$ with probability $1/n^{1/3}$. Let ${ℒ}_2$ be the set of selected vertices. Observe that this 2-step sampling to obtain ${ℒ}_2$ is equivalent to running the sampling step in Section 2 with $p=(3\ln n)/n^{2/3}$ on the entire vertex set $V$. Thus the following properties follow from Section 2 (see Proposition 4).

• $\mathrm{■}$

  $|{ℒ}_2|=O(n^{1/3}\log n)$.

• $\mathrm{■}$

  For any pair of vertices $u$ and $v$: if $|uv|\ge \lfloor n^{2/3}\rfloor$ then there is at least one vertex of ${ℒ}_2$ on $uv$.

Rather than sampling each vertex of $V$ with probability $p=(3\ln n)/n^{2/3}$ to get ${ℒ}_2$, we did this in two steps so that we have ${ℒ}_2\subseteq {ℒ}_1$. Let $T_1={ℒ}_1\cup S$ and let $T_2={ℒ}_2\cup S$. Our algorithm will use the following notations for any vertex $v$.

• $\mathrm{■}$

  Let $t_v$ be the vertex in $T_1$ that is nearest to $v$.

• $\mathrm{■}$

  Let $t_v^{\prime }$ be the vertex in $T_2$ that is nearest to $v$.

For each $u\in T_2$, we will keep the shortest path tree $𝒯(u)$ in $G$ rooted at $u$. However, we cannot afford to keep shortest path trees rooted at each $u\in {ℒ}_1$, since that would exceed the desired space bound. Corresponding to each $u\in {ℒ}_1$, let $\mathrm{𝖡𝖺𝗅𝗅}(u)=\{v\in V:t_v=u\}$ be the set of all vertices $v$ that regard $u$ as their nearest vertex in $T_1$.

• $\mathrm{■}$

  For each $v\in \mathrm{𝖡𝖺𝗅𝗅}(u)$, we will store the path $uv$.

• $\mathrm{■}$

  Thus we keep a truncated shortest path tree $\widehat{𝒯}(u)={\cup }_{v\in \mathrm{𝖡𝖺𝗅𝗅}(u)}uv$ in $G$ rooted at $u$ for each $u\in {ℒ}_1$.

Along with each vertex $v\in \widehat{𝒯}(u)$ where $u\in {ℒ}_1$, we also store $|uv|$, i.e., the hop length of $uv$, and the distance $\Vert uv\Vert$. Similarly, as done in Section 3, along with each vertex $v\in 𝒯(u)$, where $u\in T_2$, we store $|uv|$ and $\Vert uv\Vert$.

Below we describe the steps in our algorithm.

1. 1.

   Obtain the landmark sets ${ℒ}_1$ and ${ℒ}_2$, where ${ℒ}_2\subseteq {ℒ}_1$, as described above.

2. 2.

   For each $u\in T_2=S\cup {ℒ}_2$ do: compute the shortest path tree $𝒯(u)$ rooted at $u$ in $G$.

3. 3.

   Use Theorem 5 to construct an $ST$-exact distance oracle for the given source set $S$ and target set $T=T_2$ in $G=(V,E)$.

4. 4.

   For each $u\in {ℒ}_1$ do: compute the truncated shortest path tree $\widehat{𝒯}(u)$ rooted at $u$ in $G$.

5. 5.

   For every $v\in V$ do:

   1. (a)

      Let $t_v\in T_1=S\cup {ℒ}_1$ be the vertex in $T_1$ that is nearest to $v$.

   2. (b)

      For $1\le i\le |v{t}_v|$ do:

      • $\mathrm{■}$

        Set ${\mathrm{𝖣𝗂𝗌𝗍}}_1[v,i]=\Vert v{t}_v\diamond f_i\Vert$ where $f_i$ is the $i$-th edge from $t_v$ on $v{t}_v$.

6. 6.

   For every $u\in T_1$ do:

   1. (a)

      Let $t_u^{\prime }\in T_2$ be the vertex in $T_2$ that is nearest to $u$.

   2. (b)

      For $1\le j\le |u{t}_u^{\prime }|$ do:

      • $\mathrm{■}$

        Set ${\mathrm{𝖣𝗂𝗌𝗍}}_2[u,j]=\Vert u{t}_u^{\prime }\diamond f_j\Vert$ where $f_j$ is the $j$-th edge from $t_u^{\prime }$ on $u{t}_u^{\prime }$.

Observe that the array ${\mathrm{𝖣𝗂𝗌𝗍}}_1[v,i]$ stores for any vertex $v$, the distance $\Vert v{t}_v\diamond f\Vert$ where $f$ is the $i$-th edge from $t_v$ on the path $v{t}_v$. Similarly, the array ${\mathrm{𝖣𝗂𝗌𝗍}}_2[u,j]$ stores for any vertex $u\in T_1$, the distance $\Vert u{t}_u^{\prime }\diamond f\Vert$ where $f$ is the $j$-th edge from $t_u^{\prime }$ on the path $u{t}_u^{\prime }$.

In response to the query $Qu(s,v,f)$, the query answering algorithm first checks if $f\in sv$. As described in Section 3, this is done by checking the answers to some LCA queries in $𝒯(s)$. Let us assume $f\in sv$, otherwise the query answering algorithm will return $\Vert sv\Vert$.

Then the query answering algorithm looks up $x=t_v$ and $y=t_x^{\prime }$. In more detail, (i) $x$ is the closest vertex to $v$ in $T_1$ and (ii) $y$ is the closest vertex to $x$ in $T_2$. The query answering algorithm needs to know if $f\in vx$ or not; if so, it also needs to know the index $i\in \{1,\mathrm{\dots },n^{1/3}\}$ such that $f$ is the $i$-th edge on $xv$. As described in Section 3, we can decide if $f\in vx$ or not via LCA queries on the truncated shortest path tree $\widehat{𝒯}(x)$. If so, we can also obtain from $\widehat{𝒯}(x)$ the value $i$ such that $f$ is the $i$-th edge from $x$ on $xv$.

Thus the query answering algorithm knows in $O(1)$ time whether $f\in xv$ or not and if so, the index $i$ such that $f$ is the $i$-th edge from $x$ on $xv$.

• $\mathrm{■}$

  If $f\notin vx$ then $\Vert vx\diamond f\Vert =\Vert vx\Vert$; else $\Vert vx\diamond f\Vert ={\mathrm{𝖣𝗂𝗌𝗍}}_1[v,i]$.

Recall that we compute $𝒯(u)$ for all $u\in T_2$. Thus, as described in Section 3, we can efficiently check if $f\in xy$ or not; if so, the algorithm also knows the index $j$ such that $f$ is the $j$-th edge from $y$ on the path $xy$.

• $\mathrm{■}$

  If $f\notin xy$ then $\Vert xy\diamond f\Vert =\Vert xy\Vert$; else $\Vert xy\diamond f\Vert ={\mathrm{𝖣𝗂𝗌𝗍}}_2[x,j]$.

Since $s\in S$ and $y\in T_2$ (recall that $T=T_2$), the distance $\Vert ys\diamond f\Vert$ is obtained by querying the $ST$-distance oracle. Thus the query answering algorithm can obtain $\Vert vx\diamond f\Vert ,\Vert xy\diamond f\Vert$, and $\Vert ys\diamond f\Vert$ in $O(1)$ time. In response to the query $Qu(s,v,f)$, the query answering algorithm returns $\Vert vx\diamond f\Vert +\Vert xy\diamond f\Vert +\Vert ys\diamond f\Vert$.

We will show in Lemma 9 that our $s$-$v$ distance estimate in $G-f$ is at most $13\Vert sv\diamond f\Vert$.

Suppose the query is $Qu(s,v,f)$. If $f\notin sv$ then the algorithm returns $\Vert sv\Vert$, thus the stretch is 1 in this case. So assume $f\in sv$. Then the query answering algorithm returns $\Vert vx\diamond f\Vert +\Vert xy\diamond f\Vert +\Vert ys\diamond f\Vert$, where $x=t_v$ and $y=t_x^{\prime }$. Let us bound the stretch.

We need to compare the sum $\Vert vx\diamond f\Vert +\Vert xy\diamond f\Vert +\Vert ys\diamond f\Vert$ with $\Vert sv\diamond f\Vert$. Let us first show the following claim.

It follows from the definition of $T_1={ℒ}_1\cup S$ that both $x$ and $s$ are in $T_1$. Since $x$ is the nearest vertex in $T_1$ to $v$, we have $\Vert vx\Vert \le \Vert vs\Vert$. Recall that $y=t_x^{\prime }$. Since $y$ is the closest vertex in $T_2$ to $x$, we have $\Vert xy\Vert \le \Vert x{t}_v^{\prime }\Vert$, i.e., the $x$-$y$ distance is at most the distance between $x$ and $t_v^{\prime }$ (recall that $t_v^{\prime }$ is the nearest vertex in $T_2$ to $v$). Furthermore, $\Vert x{t}_v^{\prime }\Vert \le \Vert xv\Vert +\Vert v{t}_v^{\prime }\Vert$.

Observe that both $\Vert xv\Vert$ and $\Vert v{t}_v^{\prime }\Vert$ are at most $\Vert sv\Vert$ since $s\in T_1\cap T_2$, so $v$’s distance to its nearest vertex in $T_1$ and also in $T_2$ is at most $\Vert sv\Vert$. Thus $\Vert xy\Vert \le 2\Vert sv\Vert$. So we have $\Vert ys\Vert \le \Vert sv\Vert +\Vert vx\Vert +\Vert xy\Vert \le \Vert sv\Vert +\Vert sv\Vert +2\Vert sv\Vert =4\Vert sv\Vert$. $\mathrm{⊲}$

We are now ready to bound $\Vert vx\diamond f\Vert +\Vert xy\diamond f\Vert +\Vert ys\diamond f\Vert$. There are 8 cases depending on the presence of edge $f$ on various shortest paths.

1. 1.

   $f\notin vx$ and $f\notin xy$ and $f\notin ys$. Then the algorithm returns $\Vert vx\Vert +\Vert xy\Vert +\Vert ys\Vert$.

   • $\mathrm{■}$

     It immediately follows from Claim 10 that the $s$-$v$ distance estimate returned in this case is at most $7\Vert sv\Vert \le 7\Vert sv\diamond f\Vert$.

2. 2.

   $f\notin vx$ and $f\notin xy$ and $f\in ys$. Then the algorithm returns $\Vert vx\Vert +\Vert xy\Vert +\Vert ys\diamond f\Vert$. Since the failed edge $f$ belongs to neither $vx$ nor $xy$, we have $\Vert sy\diamond f\Vert \le \Vert sv\diamond f\Vert +\Vert vx\Vert +\Vert xy\Vert$. We have $\Vert vx\Vert +\Vert xy\Vert \le 3\Vert sv\Vert$ (by Claim 10).

   • $\mathrm{■}$

     Thus the $s$-$v$ distance estimate returned in this case is at most $\Vert sv\diamond f\Vert +6\Vert sv\Vert \le 7\Vert sv\diamond f\Vert$ (by Claim 10).

3. 3.

   $f\notin vx$ and $f\in xy$ and $f\notin ys$. Then the algorithm returns $\Vert vx\Vert +\Vert xy\diamond f\Vert +\Vert ys\Vert$. Observe that $G-f$ has an $x$-$y$ path of length at most $\Vert xv\Vert +\Vert vs\diamond f\Vert +\Vert sy\Vert$. Since $\Vert ys\Vert \le 4\Vert vs\Vert$ (by Claim 10), this $x$-$y$ path in $G-f$ is of length at most $\Vert sv\Vert +\Vert sv\diamond f\Vert +4\Vert sv\Vert =5\Vert sv\Vert +\Vert sv\diamond f\Vert$.

   • $\mathrm{■}$

     Using Claim 10 to bound $\Vert vx\Vert$ and $\Vert ys\Vert$, the $s$-$v$ distance estimate returned in this case is at most $\Vert sv\Vert +5\Vert sv\Vert +\Vert sv\diamond f\Vert +4\Vert sv\Vert =10\Vert sv\Vert +\Vert sv\diamond f\Vert \le 11\Vert sv\diamond f\Vert$.

4. 4.

   $f\in vx$ and $f\notin xy$ and $f\notin ys$. Then the algorithm returns $\Vert vx\diamond f\Vert +\Vert xy\Vert +\Vert ys\Vert$. Observe that $G-f$ has a $v$-$x$ path of length at most $\Vert vs\diamond f\Vert +\Vert sy\Vert +\Vert yx\Vert$. This is of length at most $\Vert sv\diamond f\Vert +4\Vert sv\Vert +2\Vert sv\Vert =6\Vert sv\Vert +\Vert sv\diamond f\Vert$.

   • $\mathrm{■}$

     Using Claim 10 to bound $\Vert xy\Vert$ and $\Vert ys\Vert$, the $s$-$v$ distance estimate returned in this case is at most $\Vert sv\diamond f\Vert +6\Vert sv\Vert +2\Vert sv\Vert +4\Vert sv\Vert =12\Vert sv\Vert +\Vert sv\diamond f\Vert \le 13\Vert sv\diamond f\Vert$.

5. 5.

   $f\notin vx$ and $f\in xy$ and $f\in ys$. Consider the shortest path tree $𝒯(x)$ rooted at $x$ in $G$. Since $f\notin vx$ and $f\in xy$, the edge $f\in wy$ where $w={\mathrm{𝖫𝖢𝖠}}_{𝒯(x)}(v,y)$. But the edge $f$ also belongs to $ys$ and $sv$ – this is not possible (see Figure 4). Thus this case cannot arise.

6. 6.

   $f\in vx$ and $f\notin xy$ and $f\in ys$. Consider the shortest path tree $𝒯(s)$ rooted at $s$ in $G$ and let $z={\mathrm{𝖫𝖢𝖠}}_{𝒯(s)}(v,x)$. Since $f\in sv$ and $f\in vx$, it follows that $f\in zv$. Hence $f\notin sx$. Thus there is a $v$-$x$ path in $G-f$ of length $\Vert vs\diamond f\Vert +\Vert sx\Vert$. Since $\Vert sx\Vert \le \Vert sv\Vert +\Vert vx\Vert \le 2\Vert sv\Vert$, this $v$-$x$ path in $G-f$ has length $\Vert sv\diamond f\Vert +2\Vert sv\Vert$.

   Since $f\in sv$ and $f\in sy$, the edge $f\in sr$ where $r={\mathrm{𝖫𝖢𝖠}}_{𝒯(s)}(v,y)$. Thus the edge $f$ does not belong to the path $v$-$r$-$y$ in $𝒯(s)$. Hence there is an $s$-$y$ path in $G-f$ of length $\Vert sv\diamond f\Vert +\Vert vs\Vert +\Vert sy\Vert \le \Vert sv\diamond f\Vert +\Vert vs\Vert +4\Vert sv\Vert$ (by Claim 10).

   • $\mathrm{■}$

     Thus $G-f$ has an $s$-$y$ path of length $\Vert sv\diamond f\Vert +5\Vert vs\Vert$, plus a $v$-$x$ path of length $\Vert sv\diamond f\Vert +2\Vert vs\Vert$. Since $\Vert xy\Vert \le 2\Vert vs\Vert$, the $s$-$v$ distance estimate returned in this case is at most $2\Vert sv\diamond f\Vert +9\Vert vs\Vert \le 11\Vert sv\diamond f\Vert$.

7. 7.

   $f\in vx$ and $f\in xy$ and $f\notin ys$. As seen in case 6, there is a $v$-$x$ path in $G-f$ of length $\Vert sv\diamond f\Vert +2\Vert vs\Vert$. Moreover, since $f\in vx$ and $f\in xy$, the edge $f\in xw$ where $w={\mathrm{𝖫𝖢𝖠}}_{𝒯(x)}(v,y)$. Hence the edge $f$ does not belong to the path $v$-$w$-$y$ in $𝒯(x)$.

   Thus there is a $v$-$y$ path in $G-f$ of length at most $\Vert vx\Vert +\Vert xy\Vert \le 3\Vert sv\Vert$. Hence there is an $x$-$v$-$y$ path of length at most $\Vert sv\diamond f\Vert +2\Vert vs\Vert +3\Vert sv\Vert =\Vert sv\diamond f\Vert +5\Vert vs\Vert$.

   • $\mathrm{■}$

     So the $s$-$v$ distance estimate returned in this case is at most $\Vert sy\Vert +(\Vert sv\diamond f\Vert +5\Vert vs\Vert )+(\Vert sv\diamond f\Vert +2\Vert vs\Vert )$. Since $\Vert sy\Vert \le 4\Vert sv\Vert$, this is at most $2\Vert sv\diamond f\Vert +11\Vert sv\Vert \le 13\Vert sv\diamond f\Vert$.

8. 8.

   $f\in vx$ and $f\in xy$ and $f\in ys$. As seen in case 7, there is a $v$-$x$ path in $G-f$ of length $\Vert sv\diamond f\Vert +2\Vert vs\Vert$ and there is an $x$-$y$ path of length at most $\Vert sv\diamond f\Vert +5\Vert vs\Vert$. It also follows from case 7 that there is a $v$-$y$ path in $G-f$ of length at most $3\Vert sv\Vert$, thus there is an $s$-$y$ path in $G-f$ of length at most $\Vert sv\diamond f\Vert +3\Vert vs\Vert$.

   • $\mathrm{■}$

     So the $s$-$v$ distance estimate returned in this case is at most $3\Vert sv\diamond f\Vert +10\Vert sv\Vert \le 13\Vert sv\diamond f\Vert$.