Color Fault-Tolerant Distance Preservers:
Õptimal Size in Conditionally Õptimal Time

We show that if $d:={\mathrm{dist}}_{G-c}(s,t)$, then $H-c$ contains an $s\rightsquigarrow t$ path of length $d$, by induction on $d$. The base case $d=0$ is trivial. When $d>0$, the last edge $(t^{\prime },t)$ of a shortest $s\rightsquigarrow t$ path in $G-c$ is also in $H-c$ by assumption. As ${\mathrm{dist}}_{G-c}(s,t^{\prime })=d-1$, by induction hypothesis, $H-c$ contains an $s\rightsquigarrow t^{\prime }$ path of length $d-1$. Concatenating $(t^{\prime },t)$ gives the desired $s\rightsquigarrow t$ path. $◀$ Thus, the algorithm’s goal is to include $\mathrm{𝙻𝚊𝚜𝚝𝙴}(s,t\mid c)$ in $H$ for every triplet $(s,t,c)\in S\times V\times C$.

We define decreasing distance thresholds by $d_i:={(n/|S|)}^{1-\frac{i}{k+1}}$ for $i=1,2,\mathrm{\dots },k$. Additionally, we define two “trivial thresholds” by $d_0:=n$ and $d_{k+1}:=1$. We use the following terminology: Two vertices $u,v\in V$ are said to be $i$-near if ${\mathrm{dist}}_G(u,v)\le 2d_i$, and $i$-far otherwise. The factor $2$ is due to technical reasons, which will become apparent shortly (in the proof of Lemma 9).

Next, for each nontrivial threshold $d_i$, $i=1,2\mathrm{\dots },k$, we construct a corresponding hitting set $A_i\subseteq V$ of size $|A_i|=O(\frac{n}{d_i}\log n)=O(n^{\frac{i}{k+1}}\cdot {|S|}^{1-\frac{i}{k+1}}\log n)$, with the following property:

1. (P)

   For every $s\in S$, $t\in V$, and color $c$, if $P$ is a contiguous subpath of $\pi (s,t\mid c)$ of length $|P|\ge d_i$, then $P$ contains some vertex from $A_i$.

This is achieved by taking $A_i$ to be a random vertex subset of size $\mathrm{\Theta }(\frac{n}{d_i}\cdot \log n)$, ensuring Property (P) w.h.p. by standard hitting set arguments. We call the vertices in $A_i$ the $i$-landmarks. Note that $|A_i|$ is increasing with $i$. We also define the $0$-landmarks as $A_0=S$, and there are no $(k+1)$-landmarks.

The algorithm works in $k+1$ levels, numbered as $i=0,1,\mathrm{\dots },k$. Each level only “cares about” including the last edges corresponding to triplets $(s,t,c)$ such that the distances between the target $t$ and the vertices of color $c$ are well-structured, as in the following definition.

The strategy of dividing into levels indeed suffices for including the last edges for all triplets, as shown by the following observation:

Let $x_1,\mathrm{\dots },x_{\mathrm{\ell }}$ be the vertices of color $c$, ordered such that ${\mathrm{dist}}_G(x_1,t)\ge \mathrm{\cdots }\ge {\mathrm{dist}}_G(x_{\mathrm{\ell }},t)$. Recall that $\mathrm{\ell }\le k$. Let $i=\min \{0\le j\le \mathrm{\ell }\mid j=\mathrm{\ell }\text{, or }{\mathrm{dist}}_G(x_{j+1},t)\le 2d_{j+1}\}$. Then

so $x_1,\mathrm{\dots },x_i$ are $i$-far from $t$, and $x_{i+1},\mathrm{\dots },x_{\mathrm{\ell }}$ are $(i+1)$-near to $t$. So, $(s,t,c)$ is in level $i$. $◀$

The main tool we use to exploit the nice distances structure of $i$-level triplets is formalized in the following Lemma 9; while its proof is simple, it plays a crucial role in our algorithm. Intuitively, it allows us to convert a level-$i$ triplet $(s,t,c)$ into a corresponding highly-structured triplet $(z,t,c)$ where $z\in A_i\cup S$, such that $\mathrm{𝙻𝚊𝚜𝚝𝙴}(s,t\mid c)=\mathrm{𝙻𝚊𝚜𝚝𝙴}(z,t\mid c)$. Thus, we think of $A_i\cup S$ as the sources for level $i$, or $i$-sources for short. Instead of treating level-$i$ triplets $(s,t,c)$ directly, we will treat all those highly-structured triplets $(z,t,c)\in (A_i\cup S)\times V\times C$ and aim to include the last edges corresponding to them.

While this approach requires us to consider a larger number of sources ($A_i\cup S$ instead of $S$), it comes with major benefits reflected in the structure. First, for a given $i$-source $z$, we will only care about targets $t$ lying inside the ball $B_G(z,d_i)$. Second, we will also only care about colors that appear at most $k-i$ times in this ball $B_G(z,d_i)$, so the “effective size” of the faulty set of vertices gets smaller. Furthermore, all these appearances of color $c$ are concentrated in a much smaller ball, of radius roughly $d_{i+1}$, around the target.

If ${\mathrm{dist}}_{G-c}(s,t)\le d_i$ we take $z=s$, and otherwise we can take some $z\in A_i$ found on the $d_i$-suffix of $\pi (s,t\mid c)$, which exists by property (P). Then (1) clearly holds. For (2), observe that ${\mathrm{dist}}_G(x,t)\le {\mathrm{dist}}_G(x,z)+{\mathrm{dist}}_G(z,t)\le 2d_i$, so $x$ is $i$-near to $t$. Since $(s,t,c)$ is in level $i$, any $c$-colored vertex that is not $i$-far from $t$ must be $(i+1)$-near to $t$, hence $x$ is $(i+1)$-near to $t$. Item (3) follows immediately from (2) by triangle inequality. Finally, (4) follows from (2): indeed, because $(s,t,c)$ is in level $i$, there are $i$ vertices of color $c$ that are $i$-far from $t$. As the $c$-colored vertices in $B_G(z,d_i)$ are $(i+1)$-near to $t$, they can be at most $k-i$. $◀$

We are now ready to give an overview of the algorithm. First, we explain how the last level is easily dealt with, and afterwards we only focus on the other levels. As a first step, we give a simple algorithm that achieves near-optimal size for the output, but has suboptimal running time. Then, we explain the high-level ideas for improving the running time to near-optimal.

Item 4 in Lemma 9 makes the last level, i.e., $i=k$, particularly easy to deal with: We simply compute the SSSP (single-source shortest path) trees rooted at each $k$-source $z\in A_k\cup S$, and include all these trees in the output $H$. This adds $O(n\cdot |A_k\cup S|)$ edges and takes $O(m\cdot |A_k\cup S|)$ time, which is easily verified to be within our budget. To see the correctness, consider some level-$k$ triplet $(s,t,c)$. By Lemma 9, there is some $z\in A_k\cup S$ on the $d_k$-suffix of $\pi (s,t\mid c)$ (item 1), and $B_G(z,d_k)$ contains no $c$-colored vertices (item 4). Hence, the $d_k$-length suffix of $\pi (s,t\mid c)$ is simply $\pi (z,t)$, which is the $z\rightsquigarrow t$ path in the tree rooted at $z$.

Let us fix some non-last level $0\le i\le k-1$. As in the last level, we still compute SSSP trees from the $i$-sources as a preprocessing step: For every $i$-source $z\in A_i\cup S$, we execute SSSP from $z$ in $G$, but trim it at distance $d_i$; The resulting rooted tree $T(z)$ is the shortest path tree from $z$ inside the ball $B_G(z,d_i)$. We add all trees $T(z)$ to the output $H$. Again, this adds $O(n\cdot |A_i\cup S|)$ edges and takes $O(m\cdot |A_i\cup S|)$ time, which is within budget.

Now, fix an $i$-source $z\in A_i\cup S$. By Lemma 9(1), we only care about adding $\mathrm{𝙻𝚊𝚜𝚝𝙴}(z,t\mid c)$ for triplets $(z,t,c)$ where $t\in B_G(z,d_i)$, i.e., $t\in T(z)$. In this case, $\pi (z,t)$, which is the $T(z)$-path from the root $z$ to $t$, is already in $H$. So, if $\pi (z,t)$ avoids the color $c$, then $(z,t,c)$ is already taken care of. We therefore assume that $t$ has some ancestor $x$ of color $c$ in $T(z)$. But by Lemma 9(2) we have ${\mathrm{dist}}_G(x,t)\le 2d_{i+1}$, meaning $x$ is in fact within the $2d_{i+1}$ nearest ancestors to $t$.

In other words, to treat the $i$-source $z$, it’s enough to add $\mathrm{𝙻𝚊𝚜𝚝𝙴}(z,t\mid c)$ whenever the target $t$ sees the color $c$ among its $2d_{i+1}$ nearest ancestors in $T(z)$. Thus, each target $t$ only causes the insertion of up to $2d_{i+1}$ edges when processing a specific $i$-source $z$, hence $|A_i\cup S|\cdot 2d_{i+1}$ edges overall (in level $i$). Summing over $t\in V$, the total number of added edges in level $i$ is at most $n\cdot |A_i\cup S|\cdot 2d_{i+1}=\tilde{O}(n^2\cdot \frac{d_{i+1}}{d_i})=\tilde{O}(n^{2-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$, as required.

By the discussion above, we get the following simple algorithm for level $i$: For each $i$-source $z\in A_i\cup S$ and color $c$, run SSSP from $z$ in $G-c$, but add to $H$ only the last edges of the shortest paths $\pi (z,t\mid c)$ such that $t$ has the color $c$ among its $2d_{i+1}$ nearest ancestors in $T(z)$. This simple algorithm is already enough to ensure the output $H$ is a CFT $S\times V$ distance preserver of the required size. However, the running time is $O(m\cdot |A_i\cup S|\cdot n)$, which in level $k-1$ becomes $\tilde{O}(m{n}^{2-\frac{2}{k+1}}{|S|}^{\frac{2}{k+1}})$. This is larger than our desired running time by a factor of $n^{1-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}}$.

The main challenge lies in improving the running time to near-optimal. Roughly, the idea is to harness the same argument we used for bounding the size of the output $H$, to also effectively bound the running time: if we could restrict each edge to participate in only $\tilde{O}(d_{i+1})$ SSSP computations from a specific $i$-source $z$, we would get total running time of $\tilde{O}(m\cdot |A_i\cup S|\cdot d_{i+1})=\tilde{O}(m{n}^{1-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$ which is precisely our budget. Intuitively, to achieve this, we would like the SSSP computation from $z$ in $G-c$ to only use edges incident on vertices $t$ such that the color $c$ appears on their nearest $\tilde{O}(d_{i+1})$ ancestors; these “allowed” edges are the only ones we might actually need to add into $H$ as a result of this computation. Clearly, this intuition doesn’t work as is: e.g., it could be that all edges incident on $z$ are not allowed to be used during the SSSP computation from $z$, which is absurd.

To make it work, instead of executing the SSSP directly on $G-c$, we construct a shortcutted graph $\widehat{G}(z,c)$ that has the allowed original edges, plus extra weighted shortcut edges which represent safe paths avoiding the color $c$.

We put two types of shortcuts in $\widehat{G}(z,c)$. The simpler ones represent paths in $T(z)$ that are unaffected by the failure of color $c$. Roughly speaking, these simple shortcuts let the SSSP computation “get inside” the subtrees of the $c$-colored vertices. However, the allowed edges are found only in the shallow layers of these subtrees (the first $\tilde{O}(d_{i+1})$ layers), while shortest paths from $z$ avoiding $c$ may need to travel into deep layers, even if they end in the shallow ones.

The second, more complicated type of shortcuts is designed to represent such traversals in the deep layers. These use the fact that the $(i+1)$-landmarks $A_{i+1}$ must appear on the path at least once every $d_{i+1}$ steps. The idea is to create a shell of additional $\tilde{O}(d_{i+1})$ layers beneath the original shallow layers, which we now call the kernel layers. We also allow the edges touching the shell to be used, which is within budget. Now, to go from between the kernel layers and the deep layers beneath the shell, one must walk through the shell for at least $d_{i+1}$ steps, and hit some $(i+1)$-landmark there. Thus, we can add shortcuts to the $(i+1)$-landmarks in the shell, which represent paths that entirely avoid the kernel (and hence the color $c$); these take care of representing the traversal into deep layers.

As it turns out, the shortcut edges are few enough so that they do not hinder the overall running time of the SSSP computations in the shortcutted graphs $\widehat{G}(z,c)$. However, the second-type shortcuts present a problem: how do we compute their weights in the first place? We need those weights just to construct $\widehat{G}(z,c)$. A priori, this requires computing distance in $G$ minus the kernel layers, which depend on the color $c$, and is therefore too costly. We overcome this obstacle by using (a variant of) the well-known tool of sparse neighborhood covers. Essentially, each cluster in the neighborhood cover will be used to define the kernel layers and shell layers for many different colors $c$, and thus we can compute the shortcuts for avoiding the kernels of the different clusters (instead of different colors), which can be done efficiently.

For each $i$-source $z\in A_i\cup S$, we execute SSSP in $G$ from the root $z$. Let $T(z)$ be the resulting shortest-path tree, but trimmed at depth $d_i$. We add all trees $T(z)$ to the output $H$. This adds $O(n\cdot |A_i\cup S|)$ edges and takes $O(m\cdot |A_i\cup S|)$ time, which is easily verified to be within our budget. Note that this step also yields the distance ${\mathrm{dist}}_G(z,v)$ between any $i$-source $z\in A_i\cup S$ and any vertex $v$. We will later use these distances as weights for shortcuts in the shortcutted graphs, as explained in the overview.

An $r$-neighborhood cover is a collection of vertex-subsets called clusters, such that every vertex has its $r$-radius ball contained in some cluster. The quality of a neighborhood cover is measured by two parameters that one wishes to minimize: The diameter of the clusters, and their overlap which is the maximum number of clusters having some vertex common to all of them. For our purposes, we need a variant of neighborhood cover, where each cluster consists of an inner kernel and shell, and the kernels themselves already cover all the $r$-neighborhoods. Formally, we use the following result:

Lemma 10 follows as a corollary from the classical near-linear time algorithm for neighborhood covers (without kernels) of [3]. We provide the proof in Appendix A.

For level $i$, we apply Lemma 10 with $r:=4d_{i+1}$, where this choice of radius stems from item 3 of Lemma 9. From now on, $K_1,\mathrm{\dots },K_{\mathrm{\ell }}$, $X_1,\mathrm{\dots },X_{\mathrm{\ell }}$ and $Y_1,\mathrm{\dots },Y_{\mathrm{\ell }}$ denote the kernels, clusters and shells resulting from this application.

As explained in the overview, the shortcutted graphs will have weighted shortcut edges based on the neighborhood cover. These shortcuts will correspond to distances from the following set:

Namely, for each $(i+1)$-landmark $a\in A_{i+1}$ and each $j$ such that $a$ belongs to the shell $Y_j$, we need to compute SSSP in $G-K_j$, i.e., avoiding the kernel $K_j$. By the overlap guarantee in Lemma 10, each $(i+1)$-landmark appears in $O(\log n)$ shells, and hence triggers only $O(\log n)$ SSSP calls. Thus, the total time spent for computing these distances is $\tilde{O}(m\cdot |A_{i+1}|)\le \tilde{O}(m\cdot |A_k|)=\tilde{O}(m\cdot n^{1-\frac{1}{k+1}}\cdot {|S|}^{\frac{1}{k+1}})$, which is within budget.

We also use the neighborhood cover to define the notion of relevant colors:

The reasoning behind the name “relevant” stems from Lemma 9(3): it says that an $i$-source $z$ should only care about colors $c$ such that the $c$-colored vertices in $B_G(z,d_i)$ are within distance $4d_{i+1}$ from each other, and hence the covering kernel of any one of them would contain all of them. To check if some color $c$ is relevant for some $i$-source $z$ only takes $\tilde{O}(1)$ time, since each vertex in $V_c\cap B_G(z,d_i)$ only belongs to $O(\log n)$ kernels, and $|V_c|\le k=O(\log n)$. Thus, computing all pairs of $i$-sources and relevant colors takes time ${\sum }_{z\in A_i\cup S}\tilde{O}(|B_G(z,d_i)|)\le |A_k\cup S|\times \tilde{O}(m)=\tilde{O}(m\cdot n^{1-\frac{1}{k+1}}\cdot {|S|}^{\frac{1}{k+1}})$, which is within budget.

Fix an $i$-source $z\in A_i\cup S$ and relevant color $c$. We now give the construction of the corresponding shortcutted graph $\widehat{G}(z,c)$. We first introduce some notations and terminologies. To avoid clutter, in the following we may omit $z,c$ from the notations when they are clear from context.

• $\mathrm{■}$

  The ball refers to $B:=B_G(z,d_i)$, and the tree refers to the shortest paths tree $T:=T(z)$ from $z$ in $B$, which was computed in Step 1.

• $\mathrm{■}$

  A vertex $v\in B$ is called affected if it is a descendant of some $c$-colored vertex in the tree $T$, and the set of affected vertices is denoted by $D:=D(z,c)$.

• $\mathrm{■}$

  The kernel, cluster, and shell refer to $K:=K(z,c)$, $X:=X(z,c)$, and $Y:=Y(z,c)$ from Definition 11, respectively. Recall that the cluster is the $4d_{i+1}$-radius ball around the kernel, i.e., $X=B_G(K,4d_{i+1})$, and the shell is the part of the cluster outside the kernel, i.e., $Y=X-K$.

• $\mathrm{■}$

  The affected kernel, affected cluster and affected shell are the intersections of the kernel, cluster and shell with the affected set $D$, denoted $K_D$, $X_D$ and $Y_D$ respectively.

• $\mathrm{■}$

  The designated landmarks $L:=L(z,c)$ are all those $(i+1)$-landmarks found in the affected shell. That is, $L=A_{i+1}\cap Y_D$.

• $\mathrm{■}$

  The outer layer $O:=O(z,c)$ are all those vertices in $B$ that have some neighbor from the affected cluster, but are not affected themselves. That is, $O=N_G(X_D)\cap (B-D)$.

We define the shortcut graph for $z$ and $c$ as follows (see verbal description following the formal definition below).

The vertex set of $\widehat{G}$ is just the ball $B$. We include in $\widehat{G}$ every original edge from $G$ that has some endpoint in the affected cluster $X_D$ (and the other endpoint can be anywhere in $B$). These original edges are given weight $1$. Then, we add two types of shortcut edges to $\widehat{G}$. One type is the landmark shortcuts: From each designated landmark $a\in L$, we add edges to every vertex $v$ outside the kernel $K$, with weight ${\mathrm{dist}}_{G-K}(a,v)$. The other type is the root shortcuts: First, we add edges from the root $z$ to every vertex $v$ in the outer layer $O$, with weight ${\mathrm{dist}}_G(z,v)$. Additionally, in the “non-degenerate” case where $L\ne \mathrm{\varnothing }$, i.e., there is some designated landmark, we add such root shortcuts from $z$ to every $v\in B-(K\cup D)$, i.e., $v$ is a non-affected vertex outside the kernel. (The reason behind this slight complication is rather technical. Essentially, if $L=\mathrm{\varnothing }$, then the latter kind of root shortcuts are not required for us, but including them might damage the running time.)

We defer the analysis of the time it takes to construct the shortcut graphs, as it is more convenient to analyze together with the time to execute the next Step 5.

For every pair of $i$-source $z\in A_i\cup S$ and relevant color $c$, we consider the corresponding shortcutted graph $\widehat{G}=\widehat{G}(z,c)$. We execute (weighted) SSSP from $z$ in $\widehat{G}-c$. Then, for each target vertex $t$ in the affected kernel $K_D$, we add the last edge of the $z\rightsquigarrow t$ shortest path computed by this SSSP into the output $H$. Note that this edge must be original, since shortcuts do not touch the affected kernel.

This concludes the description of the algorithm for level $i$. Next, we provide an analysis of the output size and running time (for steps 4 and 5). Afterward, we provide the correctness proof for the algorithm.

Let $v\in X_D(z,c)$. Then, because $v$ is affected, it has some $c$-colored ancestor $x$ in $T(z)$. Since $c$ is a relevant color for $z$, the corresponding cluster $X(z,c)$ (in fact, even its kernel $K(z,c)$) contains every $c$-colored vertex in $T(z)$, and particularly $x$. As clusters have weak diameter $O(d_{i+1}\log n)$, the distance between $x$ and $v$ in $G$, and hence also in the shortest-path tree $T(z)$, is $O(d_{i+1}\log n)$. $◀$

First, we analyze the number of edges added to the output $H$ during level $i$. Each subroutine for pair $z,c$ adds as many edges as the size of the affected kernel. So, by Lemma 12, the total number of added edges during level $i$ is $|V|\cdot |A_i\cup S|\cdot O(d_{i+1}\log n)=\tilde{O}(n^2\cdot \frac{d_{i+1}}{d_i})=\tilde{O}(n^{2-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$, which is within our budget.

We now focus on the running time. To start, let us consider the time required to construct the shortcutted graphs. The primary task here is to identify the vertices in the affected kernel/cluster/shell. By Lemma 12, this can be done by scanning the subtrees rooted in the $c$-colored vertices in $T(z)$, but only up to depth $O(d_{i+1}\log n)$ from the root of the subtree, and checking if the scanned vertices belong to the corresponding kernel/cluster/shell. Thus, fixing $z$ and letting $c$ vary, each edge in $T(z)$ is scanned only $O(d_{i+1}\log n)$ times. Now summing over $z$, we bound the running time for identifying all affected clusters by $m\cdot |A_i\cup S|\cdot O(d_{i+1}\log n)=\tilde{O}(mn\frac{d_{i+1}}{d_i})=\tilde{O}(m{n}^{1-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$, which is within budget. Once the affected kernel/cluster/shell (and the designated landmarks inside the affected shell) are identified, the rest of the time to construct the shortcutted graph $\widehat{G}(z,c)$ is linear in the number of edges (original or shortcuts) that $\widehat{G}(z,c)$ has. The SSSP we execute in this $\widehat{G}(z,c)$ is also near-linear in the number of edges; hence, it remains to account for the time required to run the SSSPs in the shortcutted graphs.

Observe that the number of edges in $\widehat{G}(z,c)$ is dominated by its original edges and its landmark shortcuts. Indeed, a root shortcut of the form $(z,v)$ with $v\in O$ can be charged to some original edge $(v,u)$ with $u\in X_D$. Also, a root shortcut of the form $(z,v)$ with $v\in B-(K\cup D)$ can be charged to a landmark shortcut $(a,v)$ with $a\in L$. Now, recall that original edges and landmark shortcuts have at least one endpoint in the affected cluster. Thus, by Lemma 12, each original edge $e\in E$ can appear in at most $|A_i\cup S|\cdot O(d_{i+1}\log n)=\tilde{O}(n\frac{d_{i+1}}{d_i})=\tilde{O}(n^{1-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$ shortcutted graphs. Similarly, each pair in $A_{i+1}\times V$ can appear as a landmark shortcut (with varying weight) in $\tilde{O}(n^{1-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$ shortcutted graphs. So, summing over all pairs $z,c$, the total time for level $i$ (other than the preprocessing, which we already accounted for) is

Note that $|A_{i+1}|\cdot n\le |A_k|\cdot n=\tilde{O}(n^{2-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})\le \tilde{O}(m)$, so the total running time of level $i$ is $\tilde{O}(m{n}^{1-\frac{1}{k+1}}{|S|}^{\frac{1}{k+1}})$ as needed.

1. (1)

   By Lemma 9(1), ${\mathrm{dist}}_{G-c}(z,t)\le d_i$, so $\pi (z,t\mid c)$ cannot leave the $d_i$-ball $B$ around $z$.

2. (2)

   This follows as shortcuts in $\widehat{G}$ correspond to paths in $G-(V_c\cap B)$. Indeed, root shortcuts correspond to paths in $T$ to unaffected vertices, which avoid the color $c$ entirely. As for landmark shortcuts, they represent paths in $G-K$, and the kernel $K$ contains $V_c\cap B$ by its definition.

$◀$

Thus, the heart of the argument lies in the following lemma, completing the correctness proof:

First, observe that once $\pi (z,t\mid c)$ enters the affected set $D$, it stays in $D$. This is because if $v\in B-D$ is some unaffected vertex, then the shortest $z\rightsquigarrow v$ in $G-c$ is simply the tree path in $T$, which only consists of unaffected vertices. We use this observation (implicitly) throughout.

Partition $\pi (z,t\mid c)$ into subpaths $P_1\circ P_2\mathrm{\cdots }\circ P_{2q}$ (last vertex of $P_j$ is first vertex of $P_{j+1}$), where the even subpaths $P_2,P_4,\mathrm{\cdots },P_{2q}$ are exactly the maximal subpaths within the affected core $K_D$. (This is well defined as $z\notin K_D$ and $t\in K_D$.) All original edges inside the affected cluster exist in $\widehat{G}$, so the even subpaths are taken care of, and we just need to argue about the odd ones.

Consider any odd subpath $P_j$ except the prefix $P_1$. If $P_j$ does not leave the affected cluster $X_D$, then $P_j$ exists in $\widehat{G}$ as is. Otherwise, $P_j$ must take its first edge from some $u\in K_D$ into some $v$ in the affected shell $Y_D$, and walk through $Y_D$ for at least $4d_{i+1}$ steps to leave the cluster (since the shell is the $4d_{i+1}$-width ring around the kernel). So by the hitting set property (P), this traversal through the shell must hit some $(i+1)$-landmark $a\in A_{i+1}\cap Y_D=L$. From $a$, $P_j$ continues outside the kernel up until its last edge connecting some $v^{\prime }\in Y_D$ to the final vertex $u^{\prime }\in K_D$. Note that the edges $(u,v)$ and $(v^{\prime },u^{\prime })$ are within the affected cluster $X_D$, and hence included in $\widehat{G}$. Also, $\widehat{G}$ has the landmark shortcuts $(v,a)$ and $(a,v)$ with weights ${\mathrm{dist}}_{G-K}(v,a)$ and ${\mathrm{dist}}_{G-K}(a,v)$, which is precisely the distances that $P_j$ travels between $v,a$, and between $a,v^{\prime }$. Thus, the path $(u,v)\circ (v,a)\circ (a,v^{\prime })\circ (v^{\prime },u)$ in $\widehat{G}-c$ corresponds to $P_j$.

It remains to consider the prefix $P_1$. Let us first handle the case where $P_1$ does not go through $D-X_D$, i.e., it only visits unaffected vertices or travels inside the affected cluster. Let $v$ be the last unaffected vertex on $P_1$. The next vertex after $v$ must be in $X_D$, meaning $v\in O$. Thus, $\widehat{G}$ has the root shortcut $(z,v)$ with weight ${\mathrm{dist}}_G(z,v)$, which is exactly the distance $P_1$ travels between $z,v$. After reaching $v$, the path $P_1$ only uses edges touching $X_D$, which exist in $\widehat{G}$. So, $P_1$ has a corresponding path in $\widehat{G}-c$ as needed.

Finally, suppose $P_1$ goes through $D-X_D$. Then, after visiting its last vertex from $D-X_D$, it must travel for at least $4d_{i+1}$ steps inside the shell $Y_D$, until it takes its final edge from some $v^{\prime }\in Y_D$ to its final vertex $u^{\prime }\in K_D$. So, by property (P), this traversal on the shell must hit some designated landmark $a\in L$ (and in particular $L\ne \mathrm{\varnothing }$). Then, $\widehat{G}$ has the landmark shortcut $(a,v^{\prime })$ of weight ${\mathrm{dist}}_{G-K}(a,v^{\prime })$, which is precisely the distance that $P_1$ travels between $a,v^{\prime }$. Also, the edge $(v^{\prime },u^{\prime })$ is within $X_D$, and thus exists in $\widehat{G}$. It remains to show that the subpath $P_1^{\prime }$ of $P_1$ between $z,a$ has a corresponding path in $\widehat{G}-c$. To this end, consider the last unaffected $u\in B-D$ vertex that $P_1^{\prime }$ visits.