Vertex fault tolerant additive spanners

Abstract

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. In this paper, we address the problem of designing a fault-tolerant additive spanner, namely, a subgraph H of the network G such that subsequent to the failure of a single vertex, the surviving part of H still contains an additive spanner for (the surviving part of) G, satisfying $\mathrm{dist}(s,t,H{\setminus } \{v\}) \le \mathrm{dist}(s,t,G{\setminus } \{v\})+\beta$ for every $s,t,v \in V$. Recently, the problem of constructing fault-tolerant additive spanners resilient to the failure of up to f edges has been considered (Braunschvig et al. Proceedings of the WG, pp 206–214, 2012). The problem of handling vertex failures was left open therein. In this paper we develop new techniques for constructing additive FT-spanners overcoming the failure of a single vertex in the graph. Our first result is an FT-spanner with additive stretch 2 and $O(n^{5/3})$ edges. Our second result is an FT-spanner with additive stretch 6 and $O(n^{3/2})$ edges. The construction algorithm consists of two main components: (a) constructing an FT-clustering graph and (b) applying a modified path-buying procedure suitably adapted to failure prone settings. Finally, we also describe two constructions for fault-tolerant multi-source additive spanners, aiming to guarantee a bounded additive stretch following a vertex failure, for every pair of vertices in $S \times V$ for a given subset of sources $S\subseteq V$. The additive stretch bounds of our constructions are 4 and 8 (using a different number of edges).

1 Introduction

An $(\alpha ,\beta )$-spanner H of an unweighted undirected graph G is a spanning subgraph satisfying for every pair of vertices $s,t \in V$ that $\mathrm{dist}(s,t,H) \le \alpha \cdot \mathrm{dist}(s,t,G)+\beta$. When $\beta =0$, the spanner is termed a multiplicative spanner and when $\alpha =1$ the spanner is additive. Clearly, additive spanners provide a much stronger guarantee than multiplicative ones, especially for long distances. Constructions of additive spanners with small number of edges are currently known for $\beta =2,4,6$ with $O(n^{3/2}), \widetilde{O}(n^{7/5})$ and $O(n^{4/3})$ edges respectively [1, 2, 5, 12, 15, 16]. This paper considers a network G that may suffer a single vertex failure event, and looks for fault tolerant additive spanners that maintain their additive stretch guarantee under failures. Formally, a subgraph $H \subseteq G$ is a $\beta$-additive FT-spanner iff for every $(s,t) \in V \times V$ and for every failing vertex $v \in V$, $\mathrm{dist}(s,t, H {\setminus } \{v\}) \le \mathrm{dist}(s,t, G {\setminus } \{v\})+\beta$. As a motivation for such structures, consider a situation where it is required to lease a subnetwork of a given network, which will provide short routes from every source s and every target t with additive stretch 2. In a failure-free environment one can simply lease a 2-additive spanner $H_0$ of the graph with $\Theta (n^{3/2})$ edges. However, if one of the vertices in the graph fails, some $s-t$ routes in $H_0 {\setminus } \{v\}$ might be significantly longer than the corresponding route in the surviving graph $G {\setminus } \{v\}$. Moreover, s and t are not even guaranteed to be connected in $H_0 {\setminus } \{v\}$. One natural approach towards preparing for such eventuality is to lease a larger set of links, i.e., an additive FT-spanner.

The notion of fault-tolerant spanners for general graphs was initiated by Chechik et al. [11] for the case of multiplicative stretch. Specifically, Chechik et al. [11] presented algorithms for constructing an f-vertex fault tolerant spanner with multiplicative stretch $(2k-1)$ and $O(f^2 k^{f+1} \cdot n^{1+1/k}\log ^{1-1/k}n)$ edges. Dinitz and Krauthgamer presented in [14], a randomized construction attaining an improved tradeoff for vertex fault-tolerant spanners, namely, f-vertex fault tolerant k-spanner with $\widetilde{O}(f^2 \cdot n^{1+2/(k+1)})$ edges. Constructions of fault-tolerant spanners with additive stretch resilient to edge failures were recently given by Braunschvig et al. [9]. They establish the following general result. For a given n-vertex graph G, let $H_1$ be an ordinary additive $(1, \beta )$ spanner for G and $H_2$ be a $(\alpha ,0)$ fault tolerant spanner for G resilient against up to f edge faults. Then $H=H_1 \cup H_2$ is a $(1, \beta (f))$ additive fault tolerant spanner for G (for up to f edge faults) for $\beta (f)=2f (2\beta +\alpha -1)+\beta$. Note that since in general the degree of a vertex in the graph might be as large as $\Theta (n)$, using the construction of [9] by removing all edges incident to the failing vertex, might result with an additive stretch of $\Theta (n)$. Fixing the number of edge faults to $f=1$, yields constructions with an additive stretch of 14 with $O(n^{3/2})$ edges and an additive stretch of 38 with $O(n^{4/3})$ edges. When fixing the number of edges in H to be $O(n^{4/3})$ edges and the number of edge faults to $f=1$ yields $\alpha =5$ and $\beta =6$. Hence, in particular, there is no construction for additive stretch $< 14$ and $o(n^2)$ edges. In addition, note that these structures are resilient only to edge failures as the techniques of [9] cannot be utilized to protect even against a single vertex failure event. Indeed, the problem of handling vertex failures was left open therein.

In this paper, we make a first step in this direction and provide additive FT-structures resilient to the failure of a single vertex (and hence also edge) event. Our constructions provide additive stretch 2 and 6 and hence provide an improved alternative also for the case of a single edge failure event, compared to the constructions of [9].

The presented algorithms are based upon two important notions, namely, replacement paths and the path-buying procedure, which have been studied extensively in the literature. For a source s, a target vertex t and a failing vertex $v\in V$, a replacement path is the shortest $s-t$ path $P_{s,t,v}$ that does not go through v. The vast literature on replacement paths (cf. [7, 17, 23, 24]) focuses on time-efficient computation of the these paths as well as their efficient maintenance in data structures (a.k.a distance oracles).

Fault-resilient structures that preserve exact distances for a given subset of sources $S \subseteq V$ have been studied in [20], which defines the notion of an FT-MBFS structure $H \subseteq G$ containing the collection of all replacement paths $P_{s,t,v}$ for every pair $(s,t) \in S \times V$ for a given subset of sources S and a failing vertex $v \in V$. Hence, FT-MBFS structures preserve the exact $s-t$ distances in $G {\setminus } \{v\}$ for every failing vertex v, for every source $s \in S$.

It is shown in [20] that for every graph G and a subset S of sources, there exists a (poly-time constructible) 1-edge (or vertex) FT-MBFS structure H with $O(\sqrt{|S|} \cdot n^{3/2})$ edges. This result is complemented by a matching lower bound showing that for sufficiently large n, there exist an n-vertex graph G and a source-set $S \subseteq V$, for which every FT-MBFS structure is of size $\Omega (\sqrt{|S|} \cdot n^{3/2})$. Hence exact FT-MBFS structures may be rather expensive. This last observation motivates the approach of resorting to approximate distances, in order to allow the design of a sparse subgraph with properties resembling those of an FT-MBFS structure.

The problem of constructing multiplicative approximation replacement paths $\widetilde{P}_{s,t,v}$ (i.e., such that $|\widetilde{P}_{s,t,v}| \le \alpha \cdot |P_{s,t,v}|$) has been studied in [3, 6, 10]. In particular its single source variant has been studied in [4, 8, 21]. In this paper, we further explore this approach. For a given subset of sources S, we focus on constructions of subgraphs that contain an approximate BFS structure with additive stretch $\beta$ for every source $s \in S$ that are resistant to a single vertex failure.

Indeed, the construction of additive sourcewise FT-spanners provides a key building block of additive FT-spanner constructions (in which bounded stretch is guaranteed for all pairs). We present two constructions of sourcewise spanners with different stretch-size tradeoffs. The first construction ensures an additive stretch 4 with $O(n \cdot |S|+ (n/|S|)^3)$ edges and the second construction guarantees additive stretch 8 with $O(n \cdot |S|+(n/|S|)^2)$. As a direct consequence of these constructions, we get an additive FT-spanner with stretch 6 and $O(n^{3/2})$ edges and an additive sourcewise FT-spanner with additive stretch 8 and $O(n^{4/3})$ for at most $O(n^{1/3})$ sources.

Additive spanners for specified pairs or sources where the objective is to construct a subgraph $H \subseteq G$ that satisfies the bounded additive stretch requirement only for a subset of pairs, are given in [13, 18, 19, 22].

Contributions This paper provides the first constructions for additive spanners resilient upon a single vertex failure. In addition, it provides the first additive FT-structures with stretch guarantee as low as 2 or 6 and with $o(n^2)$ edges.

Our constructions employ a modification of the path-buying strategy, which was originally devised in [5] to provide 6-additive spanners with $O(n^{4/3})$ edges. Recently, the path-buying strategy was employed in the context of pairwise spanners [13].

The adaptation of the path-buying strategy to the vertex failure setting has been initiated in [21] for the case of a single-source s and a single edge failure event. In this paper, we extend this technique in two senses: (1) dealing with many sources and (2) dealing with vertex failures. In particular, Parter and Peleg [21] achieves a construction of single source additive spanner with $O(n^{4/3})$ edges resilient to a single edge failure. In this paper, we extend this construction to provide a multiple source additive spanners resilient to a single vertex failure, for $O(n^{1/3})$ sources, additive stretch 8 and $O(n^{4/3})$ edges. In summary, we show the following.

Theorem 1

(2-additive FT-spanner) For every n-vertex graph $G=(V,E)$, there exists a (polynomially constructible) subgraph $H \subseteq G$ of size $O(n^{5/3})$ such that $\mathrm{dist}(s,t,H{\setminus }\{v\})\le \mathrm{dist}(s,t,G{\setminus }\{v\})+2$ for every $s,t,v \in V$.

Theorem 2

(4-additive sourcewise FT-spanner) For every n-vertex graph $G=(V,E)$ and a subset of sources $S \subset V$, there exists a (polynomially constructible) subgraph $H \subseteq G$ of size $O(|S| \cdot n+(n/|S|)^3)$ such that $\mathrm{dist}(s,t,H{\setminus }\{v\})\le \mathrm{dist}(s,t,G{\setminus }\{v\})+4$ for every $s\in S$ and $t,v \in V$.

Taking $|S|=O(\sqrt{n})$, Theorem 2 can be shown to yield the following.

Theorem 3

(6-additive FT-spanner) For every n-vertex graph $G=(V,E)$, there exists a (polynomially constructible) subgraph $H \subseteq G$ of size $O(n^{3/2})$ such that $\mathrm{dist}(s,t,H{\setminus }\{v\})\le \mathrm{dist}(s,t,G{\setminus }\{v\})+6$ for every $s,t,v \in V$.

Theorem 4

(8-additive sourcewise FT-spanner) For every n-vertex graph $G=(V,E)$ and a subset of sources $S \subset V$ where $|S|=O(n^{1/3})$, there exists a (polynomially constructible) subgraph $H \subseteq G$ of size $O(n^{4/3})$ such that $\mathrm{dist}(s,t,H{\setminus }\{v\})\le \mathrm{dist}(s,t,G{\setminus }\{v\})+8$ for every $s\in S$ and $t,v \in V$.

Techniques Our main technical contribution is in adapting the path-buying technique to the fault-tolerance setting. The high-level idea of the basic path-buying procedure (without faults) is as follows. In an initial clustering phase, a suitable clustering of the vertices is computed, and an associated subset of edges is added to the spanner. Then comes a path-buying phase, where they consider an appropriate sequence of paths, and decide whether or not to add each path into the spanner. Each path P has a cost, given by the number of edges of p not already contained in the spanner, and a value, measuring P’s help in satisfying the considered set of constraints on pairwise distances. The considered path P is added to the spanner iff its value is sufficiently larger than its cost. In our adaptation to the FT-setting, an FT-clustering graph is computed first, providing vertices with a sufficiently high degree two clusters to which it belongs. Every cluster consists of a center vertex v connected via a star to a subset of its heavy neighbors. In our design not all replacement paths are candidates to be bought in the path-buying procedure. Let $\pi (s,t)$ be an $s-t$ shortest-path between a source s and a clustered vertex t. We divide the failing events on $\pi (s,t)$ into two classes depending on the position of the failing vertex on $\pi (s,t)$ with respect to the least common ancestor (LCA) $\ell (s,t)$ of t’s cluster members in the BFS tree rooted at s. Specifically, a vertex fault $\pi (s,t)$ that occurs on $\ell (s,t)$ is handled directly by adding the last edge of the corresponding replacement path to the spanner. Vertex failures that occur strictly below the LCA, use the shortest-path $\pi (s,x)$ between s and some member x in the cluster of t such that the failing vertex v does not appear on the $\pi (s,x)$ path. The approximate replacement path will follow $\pi (s,x)$ and then use the intercluster path between x and t. The main technicality is when concerning the complementary case when that failing event occurs strictly above $\ell (s,t)$. These events are further divided into two classes depending on the structure of their replacement path. Some of these replacement paths would again be handled directly by collecting their last edges into the structure and only the second type paths would be candidates to be bought by the path-buying procedure.

2 Preliminaries

Notation Throughout, we assume that the shortest-paths in the given graph $G=(V,E)$ are unique. Specifically, the shortest path ties are broken in a consistent manner so that the subpath of a shortest-path is a shortest path itself. For a subgraph $G' \subseteq G$, let $\pi (u,v,G')$ denote the $u-v$ shortest-path in $G'$.

Given a graph $G=(V,E)$, a vertex pair s, t and an edge weight function $W: E(G)\rightarrow \mathbb R^{+}$, let SP(s, t, G, W) be the set of $s-t$ shortest-paths in G according to the edge weights of W. Throughout, we make use of (an arbitrarily specified) weight assignment W that guarantees the uniqueness of the shortest paths.¹ Hence, $SP(s, t, G', W)$ contains a single path for every $s,t \in V$ and for every subgraph $G' \subseteq G$, we override notation and let SP(s, t, G, W) be the unique $s-t$ path in G according to W. When the shortest-path are computed in G, let $\pi (s,t)=SP(s, t, G, W)$. To avoid cumbersome notation, we may omit W and simply refer to $\pi (s,t)=SP(s, t, G, W)$. For a subgraph $G' \subseteq G$, let $V(G')$ (resp., $E(G')$) denote the vertex set (resp. edge set) in $G'$.

For a given source node s, let $T_0(s)=\bigcup _{t \in V} \pi (s,t)$ be a shortest paths (or BFS) tree rooted at s. For a set $S \subseteq V$ of source nodes, let $T_0(S)=\bigcup _{s \in S} T_0(s)$ be a union of the single source BFS trees. For a vertex $t \in V$ and a subset of vertices $V' \in V$, let $T(t,V')=\bigcup _{u \in V'} \pi (u,t)$ be the union of all $\{t\} \times V'$ shortest-paths (by the uniqueness of W, $T(t,V')$ is a subtree of $T_0(t)$). Let $\Gamma (v, G)$ be the set of v’s neighbors in G. Let $E(v,G)=\{(u,v) \in E(G)\}$ be the set of edges incident to v in the graph G and let $\mathtt{deg}(v,G)=|E(v,G)|$ denote the degree of node v in G. For a given graph $G=(V,E)$ and an integer $\varDelta \le n$, a vertex v is $\varDelta$-heavy if $\mathtt{deg}(v,G) \ge \varDelta$, otherwise it is $\varDelta$-light. When $\varDelta$ is clear from the context, we may omit it and simply refer to v as heavy or light. For a graph $G=(V,E)$ and a positive integer $\varDelta \le n$, let $V_{\varDelta }=\{v ~\mid ~ \mathtt{deg}(v,G)\ge \varDelta \}$ be the set of $\varDelta$-heavy vertices in G. (Throughout, we sometimes simplify notation by omitting parameters which are clear from the context.) For a subgraph $G'=(V', E') \subseteq G$ (where $V' \subseteq V$ and $E' \subseteq E$) and a pair of vertices $u,v \in V$, let $\mathrm{dist}(u,v, G')$ denote the shortest-path distance in edges between u and v in $G'$. For a path $P=[v_1, \ldots , v_k]$, let $\mathtt{LastE}(P)$ be the last edge of P, let |P| denote its length and let $P[v_i, v_j]$ be the subpath of P from $v_i$ to $v_j$. For paths $P_1$ and $P_2$, denote by $P_1 \circ P_2$ the path obtained by concatenating $P_2$ to $P_1$. For “visual” clarity, the edges of these paths are considered throughout, to be directed away from the source node s. Given an $s-t$ path P and an edge $e=(x,y) \in P$, let $\mathrm{dist}(s, e, P)$ be the distance (in edges) between s and y on P. In addition, for an edge $e=(x,y)\in T_0(s)$, define $\mathrm{dist}(s,e)=i$ if $\mathrm{dist}(s,x,G)=i-1$ and $\mathrm{dist}(s,y,G)=i$. A vertex w is a divergence point of the s-v paths $P_1$ and $P_2$ if $w \in P_1 \cap P_2$ but the next vertex u after w (i.e., such that u is closer to v) in the path $P_1$ is not in $P_2$.

Basic Tools. We consider the following graph structures.

Definition 1

($(\alpha ,\beta ,S)$ FT-spanner) A subgraph $H \subseteq G$ is an $(\alpha , \beta ,S)$ FT-spanner structure with respect to S if for every $(s,t) \in S \times V$ and every $v \in V$, $\mathrm{dist}(s, t, H {\setminus } \{v\}) \le \alpha \cdot \mathrm{dist}(s, t, G {\setminus } \{v\})+\beta .$

Definition 2

($(\alpha , \beta )$ FT-spanners) A subgraph $H \subseteq G$ is an $(\alpha , \beta )$ FT-spanner if it is an $(\alpha , \beta ,V)$ FT-spanner for G with respect to V.

Throughout, we restrict attention to the case of a single vertex fault. When $\alpha =1$, H is termed $(\beta , S)$-additive FT-spanner. In addition, in case where $S=V$, H is an $\beta$-additive FT-spanner.

FT-Clustering graph $G_{\varDelta }$ For a subset $Z \subseteq V$, a heavy vertex $v \in V_{\varDelta }$ is said to be clustered by Z if $|\Gamma (v,G)\cap Z|\ge 2$. When Z is clear from the context, we simply say that v is clustered. A subset $Z \subseteq V$ is an FT-center set for a subset $V'$ of $\varDelta$-heavy vertices, if every vertex $v \in V'$ is clustered by Z. The FT-center set Z is constructed in the following manner. Initially, set $Z=\emptyset$. Let $V'$ be the subset of unclustered heavy vertices by Z. Hence, initially $V'=V_{\varDelta }$. As long as there exists a vertex $u \in V {\setminus } Z$ that has at least $\varDelta$ neighbors in $V'$, add u to Z and remove the clustered vertices of $\Gamma (u,G) \cap V'$ from $V'$. Let $V_C=V_{\varDelta }{\setminus } V'$ be the set of clustered heavy vertices by Z. For every clustered vertex $v \in V_C$, let $Z(v)=\{z_1(v), z_2(v)\}$ be two arbitrary neighbors of v in Z.

We then add to the graph $G_{\varDelta }$, the set of all edges incident to the unclustered vertices in $V {\setminus } V_C$, and in addition connect each clustered vertex $v \in V_C$ to Z(v). Formally,

$$\begin{aligned} G_\varDelta =\bigcup _{v \in V_{C}}\{(v,z_1(v)), (v,z_2(v))\} \cup \bigcup _{v \in V {\setminus } V_{C}} E(v,G). \end{aligned}$$

Note that every edge in $G {\setminus } G_{\varDelta }$ is incident to a clustered vertex. For every center vertex $z \in Z$, let $C_z$ be the cluster consisting of z and all the clustered vertices it represents, i.e., $C_z=\{z\} \cup \{v \in V_{C}~\mid ~ z \in Z(v)\}.$ Note that every center z is connected via a star to each of the vertices in its cluster $C_z$, hence the diameter of each cluster $C_z$ in $G_{\varDelta }$ is 2.

For a failing vertex v and a clustered vertex t, let $z_v(t) \in Z(t) {\setminus } \{v\}$ be a cluster center of t in $G{\setminus } \{v\}$. In particular, if $z_1(t)\ne v$, then $z_v(t)=z_1(t)$, else $z_v(t)=z_2(t)$. Let $C_v(t)$ be the cluster centered at $z_v(t)$. Note that since every clustered vertex has two cluster centers $z_1(t)$ and $z_2(t)$, we have the guarantee that at least one of them survives the single vertex fault event. The next observation summarizes some important properties of the clustering graph.

Observation 5

• (1) Every missing edge $e \in G {\setminus } G_{\varDelta }$ is incident to a clustered vertex v.

• (2) The diameter of every cluster $C_z$ is 2.

• (3) The FT-center set $Z \subseteq V$ is of size $|Z|=O(n/\varDelta )$.

• (4) $|E(G_{\varDelta })|=O(\varDelta \cdot n)$.

Proof

Claims (1–2) are immediate. Consider claim (3). Since every center in Z has at least $\varDelta$ neighbors in $V_{\varDelta }$ and since every vertex has two neighbors in Z before removing it from $V'$ it holds that $|Z| \cdot \varDelta \le 2n$ hence $|Z|\le 2n/\varDelta$. Consider claim (4). The number of edges incident to light vertices is bounded by $\varDelta \cdot n$. Hence, it remains to bound the edges incident to the subset of unclustered heavy vertices $V' = V_{\varDelta } {\setminus } V_C$ . Note that every vertex $u \in V{\setminus } Z$ has a most $\varDelta -1$ neighbors in $V'$. In addition, every vertex v in $V'$ has at most one neighbor in Z, hence the total number of edges in $E(V',G)$ is bounded by $\varDelta \cdot n$. The observation follows. $\square$

Replacement paths For a source s, a target vertex t and a vertex $v\in G$, a replacement path is the shortest $s-t$ path $P_{s,t,v} \in SP(s, t, G {\setminus } \{v\})$ that does not go through v.

Observation 6

Every path $P_{s,t,v}$ contains at most $3n/\varDelta$ $\varDelta$-heavy vertices.

Proof

Note that

$$\begin{aligned}&3n ~\ge ~ 3 \cdot \left| \bigcup _{x \in P_{s,t,v} \cap V_{\varDelta }}\Gamma (x,G{\setminus }\{v\})\right| \\&\quad \ge \sum _{x \in P_{s,t,v} \cap V_{\varDelta }}\mathtt{deg}(x,G{\setminus }\{v\}) \ge |P_{s,t,v} \cap V_\varDelta | \cdot \varDelta , \end{aligned}$$

where the second inequality follows by the fact the every vertex $u \in V {\setminus } \{v\}$ has at most 3 neighbors on $P_{s,t,v}$. The observation follows. $\square$

New-ending replacement paths A replacement path $P_{s,t,v}$ is called new-ending if its last edge is different from the last edge of the shortest path $\pi (s,t)$. Put another way, a new-ending replacement path $P_{s,t,v}$ has the property that once it diverges from the shortest-path $\pi (s,t)$, it joins $\pi (s,t)$ again only at the final vertex t. It is shown in [20] that for a given graph G and a set S of source vertices, a structure $H \subseteq G$ containing a BFS tree rooted at each $s \in S$ plus the last edge of each new-ending replacement path $P_{s,t,v}$ for every $(s,t) \in S \times V$ and every $v \in V$, is an FT-MBFS structure with respect to S. Our algorithms exploit the structure of new-ending replacement paths to construct $(\beta ,S)$-additive FT-spanners. Essentially, a key ingredient in our analysis concerns with collecting the last edges from a subset of new-ending replacement paths as well as bounding the number of new-ending paths $P_{s,t,v}$ whose detour segments intersect with $\pi (s',t){\setminus } \{t\}$ for some other source $s' \in S$.

The basic building block Our constructions of $\beta$-additive FT-spanners, for $\beta \ge 2$, consist of the following two building blocks: (1) an FT-clustering graph $G_{\varDelta }$ for some parameter $\varDelta$, and (2) an $(\beta -2,Z)$-additive FT-spanner $H_{\beta -2}(Z)$ where Z is an FT-center set (i.e., cluster centers) for the vertices.

Lemma 1

Let $\beta \ge 2$ and $H=G_{\varDelta } \cup H_{\beta -2}(Z)$ where Z is an FT-center set for the clustered heavy vertices $V_{C}$. Then H is an $\beta$ additive FT-spanner.

Proof

Consider vertices $u_1,u_2,u_3 \in V$. Let $P \in SP(u_1,u_2, G {\setminus } \{u_3\})$ be the $u_1-u_2$ replacement path in $G {\setminus } \{u_3\}$ and let (x, y) be the last missing edge on P that is not in H (i.e., closest to $u_2$). Since $G_{\varDelta } \subseteq H$, by Observation 5(1), y is a clustered vertex. Let $z =z_{u_3}(y)$ be the cluster center of y in $G {\setminus } \{u_3\}$, and consider the following $u_1-u_2$ path $P_3=P_1 \circ P_2$ where $P_1 \in SP(u_1, z, H {\setminus } \{u_3\})$ and $P_2 =(z,y) \circ P[y, u_2]$. Clearly, $P_3 \subseteq H {\setminus } \{u_3\}$, so it remains to bound its length. Since $H_{\beta -2}(Z) \subseteq H$, it holds that $|P_1|\le \mathrm{dist}(u_1, z, G {\setminus } \{u_3\})+\beta -2$. Hence,

$$\begin{aligned}&\mathrm{dist}(u_1, u_2, H {\setminus } \{u_3\}) \le |P_3|~=~|P_1|+|P_2|\\&\quad \le \mathrm{dist}(u_1,z, G {\setminus } \{u_3\})+\!\beta \!-2\!+\mathrm{dist}(y,u_2, G {\setminus } \{u_3\})\!+\!1\\&\quad \le \mathrm{dist}(u_1,y, G {\setminus } \{u_3\})+\mathrm{dist}(y, u_2, G {\setminus } \{u_3\})+\beta \\&\quad \le |P|+\beta ~=~\mathrm{dist}(u_1, u_2, G {\setminus } \{u_3\})+\beta , \end{aligned}$$

where the second inequality follows by the triangle inequality using the fact that the edge (z, y) exists in $H {\setminus } \{u_3\}$. The lemma follows. $\square$

3 Additive stretch 2

We begin by considering the case of additive stretch 2. We make use of the construction of FT-MBFS structures presented in [20].

Fact 7

([20]) There exists a polynomial time algorithm that for every n-vertex graph $G=(V,E)$ and a source set $S \subseteq V$ constructs an FT-MBFS structure $H_{0}(S)$ from each source $s_i \in S$, tolerant to one edge or vertex failure, with a total number of $O(\sqrt{|S|} \cdot n^{3/2})$ edges.

Set $\varDelta =\lceil n^{2/3} \rceil$ and let Z be an FT-center set (see Observation 5(3)). Let $H_{0}(Z)$ be an FT-MBFS structure with respect to the source set Z as given by Fact 7. Then, let $H=G_\varDelta \cup H_{0}(Z).$ Theorem 1 follows by Lemma 1, Observation 5 and Fact 7.

4 Sourcewise additive FT-spanners

In this section, we present two constructions of (4, S) and (8, S) additive FT-spanners with respect to a given source set $S \subseteq V$. The single source and single edge failure case (where $|S|=1$) is considered in [21], which provides a construction of a single source FT-spanner resilient against single edge failure with $O(n^{4/3})$ edges. The current construction deals with single vertex failures and increases the stretch to 8 while providing a bounded stretch for $O(n^{1/3})$ sources with the same order of edges, $O(n^{4/3})$.

4.1 Sourcewise spanner with additive stretch 4

Theorem 8

There exists a subgraph $H_{4}(S) \subseteq G$ with $O(|S| \cdot n+ (n/|S|)^{3})$ edges satisfying $\mathrm{dist}(s,t, H_{4}(S) {\setminus } \{v\})\le \mathrm{dist}(s,t,G {\setminus } \{v\})+4$ for every $(s,t) \in S\times V$ and $v \in V$.

The following notation is useful in our context. Let ${\mathcal {C}}=\{C_z ~\mid ~ z \in Z\}$ be the collection of clusters corresponding to the FT-centers Z. For a source $s\in S$ and a cluster $C_z \in {\mathcal {C}}$ rooted at FT-center $z \in Z$, let $\mathtt{LCA}(s,C_z)$ be the least common ancestor (LCA) of the cluster vertices of $C_z$ in the BFS tree $T_0(s)$ rooted at $s$. Let $\pi (s,C_z)$ be the path connecting $s$ and $\mathtt{LCA}(s,C_z)$ in $T_0(s)$.

4.1.1 Algorithm Cons4SWSpanner for constructing $H_4(S)$ spanner

Step (0): Replacement-path definition For every $(s,t) \in S \times V$ and every $v \in V$, let $P_{s,t,v}=SP(s,t, G {\setminus } \{v\},W)$.

Step (1): Clustering Set $\varDelta =|S|$ and let $Z \subseteq V$ be an FT-center set of size $O(n/\varDelta )$ (see Observation 5(3)). Let $V_C$ be the subset of heavy clustered vertices. ${\mathcal {C}}=\{C_z ~\mid ~ z \in Z\}$ be the collection of |Z| clusters. For a clustered vertex t, let $C_1(t), C_2(t)$ be its two clusters in ${\mathcal {C}}$ corresponding to the centers $z_1(t)$ and $z_2(t)$ respectively. The initial spanner is then given by $\widetilde{H}_0=T_0(S) \cup G_{\varDelta }$.

Step (2): Shortest-path segmentation For every $(s,t) \in S \times V_C$, the algorithm uses the first cluster of t, $C_1(t)$, to segment the path $\pi (s,t)$. Define

$$\begin{aligned}&\pi ^{\mathtt{far}}(s,t)=\pi (s,\ell (s,t)) {\setminus } \{\ell (s,t)\} \text{ and } \pi ^{\mathtt{near}}(s,t)\\&\quad =\pi (\ell (s,t),t){\setminus } \{\ell (s,t)\}, \end{aligned}$$

where $\ell (s,t)=\mathtt{LCA}(s,C_1(t))$ is the LCA of the cluster $C_1(t)$ in the tree $T_0(s)$. Hence, $\pi (s,t)=\pi ^{\mathtt{far}}(s,t) \circ \ell (s,t) \circ \pi ^{\mathtt{near}}(s,t)$. The algorithm handles separately vertex faults in the near and far segments. Let $V^{\mathtt{near}}(s,t)=V(\pi ^{\mathtt{near}}(s,t))$ and $V^{\mathtt{far}}(s,t)=V(\pi ^{\mathtt{far}}(s,t))$.

Step (3): Handling faults in the cluster center and the LCA Let $E^{\mathtt{local}}(t)=\{ \mathtt{LastE}(P_{s,t,v}) ~\mid ~ s \in S, v \in \{z_1(t),\mathtt{LCA}(s,C_1(t))\}\}$ and $E^{\mathtt{local}}=\bigcup _{t \in V_{C}} E^{\mathtt{local}}(t),$ be the last edges of replacement-paths protecting against the failure of the primary cluster center $z_1(t)$ and the least common ancestor $\mathtt{LCA}(s,C_1(t))$.

Step (4): Handling far vertex faults $V^{\mathtt{far}}(s,t)$ Consider the $s-t$ new-ending replacement-paths $P_{s,t,v}$ of a clustered vertex t. Let $b_{s,t,v}$ be the unique divergence point of $P_{s,t,v}$ from $\pi (s,t)$ (the uniqueness of the divergence point is guaranteed by the uniqueness of the shortest-paths, as shown in the analysis). Let $D_{s,t,v}=P_{s,t,v}[b_{s,t,v},t]$ denote the detour segment and let $D^-_{s,t,v}=D_{s,t,v}{\setminus } \{b_{s,t,v}\}$ denote the detour segment excluding the divergence point. For every clustered vertex t, let ${\mathcal {P}}^{\mathtt{far}}(t)$ be the collection of new-ending² $s-t$ paths protecting against vertex faults in the far segments, i.e., ${\mathcal {P}}^{\mathtt{far}}(t)=\{P_{s,t,v} ~\mid ~ s\in S, ~ \mathtt{LastE}(P_{s,t,v}) \notin T_0(S) \text{ and } v \in V^{\mathtt{far}}(s,t)\}$.

The algorithm divides this set into two subsets ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$ and ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$ depending on the structure of the partial detour segment $D^-_{s,t,v}$. A new-ending path $P_{s,t,v}$ is dependent if $D^-_{s,t,v}$ intersects $\pi (s',t){\setminus }\{t\}$ for some $s' \in S$, i.e., for a dependent path $P_{s,t,v}$, it holds that

$$\begin{aligned} V(D^-_{s,t,v}) \cap V(T(t,S)) \ne \{t\}. \end{aligned}$$

(1)

Otherwise, it is independent. Let

$$\begin{aligned} {\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)\!=\{P_{s,t,v} \in {\mathcal {P}}^{\mathtt{far}}(t) \mid V(D^-_{s,t,v}) \!\cap \! V(T(t,S))\!\ne \! \{t\}\} \end{aligned}$$

be the set of all $S \times \{t\}$ dependent paths and let ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)={\mathcal {P}}^{\mathtt{far}} {\setminus } {\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$ be the set of independent paths.

Step (4.1): Handling dependent new-ending paths The algorithm simply takes the last edges $E^{\mathtt{far}}_{\mathtt{dep}}(t)$ of all dependent replacement paths where $E^{\mathtt{far}}_{\mathtt{dep}}(t)=\{\mathtt{LastE}(P) ~\mid ~ P \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)\}$. Let $E^{\mathtt{far}}_{{\mathtt{dep}}}=\bigcup _{t \in V_{C}} E^{\mathtt{far}}_{\mathtt{dep}}(t)$.

In the analysis we show that dependant paths have a special structure which imposes a constraints on the cardinality of $E^{\mathtt{far}}_{\mathtt{dep}}(t)$.

Step (4.2): Handling independent new-ending paths The algorithm employs a modified path-buying procedure on the collection ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}=\bigcup _{t \in V_{C}}{\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$ of new-ending independent paths. The paths of ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$ are considered in some arbitrary order. A path $P \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$ is bought, if it improves the pairwise cluster distances in some sense. Starting with

$$\begin{aligned} G_0=T_0(S) \cup G_{\varDelta } \cup E^{\mathtt{local}} \cup E^{\mathtt{far}}_{\mathtt{dep}}, \end{aligned}$$

(2)

at step $\tau \ge 0$, the algorithm is given $G_{\tau } \subseteq G$ and considers the path $P_{\tau }=P_{s,t, v}$. Let $e=(x,y)$ be the first edge on $P_{\tau }$ which is not in $E(G_\tau )$ (where x is closer to $s$). Note that since $G_{\varDelta } \subseteq G_0$, both x and t are clustered. Recall that for a clustered vertex u and a failing vertex v, $C_v(u)$ is the cluster of u centered at $z_v(u) \in Z(u){\setminus } \{v\}$. For every cluster C, let $V_{f}(C)$ be the collection of vertices appearing on the paths $\pi (s,C)=\pi (s, \mathtt{LCA}(s,C))$ for every $s\in S$ excluding the vertices of the cluster. That is,

$$\begin{aligned} V_{f}(C)=\bigcup _{s\in S} V(\pi (s, C)){\setminus } C. \end{aligned}$$

(3)

Let $C_{1,\tau }=C_v(x)$ be the cluster of x in $G_{\varDelta } {\setminus } \{v\}$ and $C_{2,\tau }=C_v(t)$ be the cluster of t in $G_{\varDelta } {\setminus } \{v\}$. The path $P_\tau$ is added to $G_\tau$ resulting in $G_{\tau +1}=G_{\tau } \cup P_{\tau }$, only if

$$\begin{aligned} \mathrm{dist}(x, t, P_\tau )< \mathrm{dist}(C_{1,\tau }, C_{2,\tau }, G_\tau {\setminus } V_{f}(C_v(t))). \end{aligned}$$

(4)

Let $\tau '=|{\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}|$ be the total number of independent paths considered to be bought by the algorithm. Then, the algorithm outputs $H_4(S)=G_{\tau '}.$ This completes the description of the algorithm.

Analysis Throughout, we restricted attention to $s-t$ replacement paths of clustered vertices $t \in V_{C}$. Let $b_{s,t,v}$ be the first divergence point of $P_{s,t,v}$ and $\pi (s,t)$.

Lemma 2

For every vertex $u \in P_{s,t,v}$ such that $\mathtt{LastE}(P_{s,t,v}[s,u]) \notin T_0(S)$, it holds that: (a) $v \in V(\pi (s,u))$.   (b) $V(P_{s,t,v}[b_{s,t,v},u]) \cap V(\pi (s,u))=\{b_{s,t,v},u\}$.

Proof

Begin with (a). Assume towards contradiction otherwise. By the uniqueness of the weight assignment W, we get that $P_{s,t,v}[s,u]=SP(s,u, G {\setminus } \{v\},W)=\pi (s,u)$. We therefore get a contradiction to the fact that $\mathtt{LastE}(P_{s,t,v})$ not in $T_0(S)$. We next prove (b) and show that the divergence point $b_{s,t,v}$ is unique. By the definition of $b_{s,t,v}$, it occurs on $\pi (s,t)$ above the failing vertex v. Since by Lemma 2, $v \in V(\pi (s,u))$, it also holds that $b_{s,t,v} \in V(\pi (s,u))$. Assume towards contradiction that there exists an additional point

$$\begin{aligned} w \in \left( V(P_{s,t,v}[b_{s,t,v},u]) \cap V(\pi (s,u))\right) {\setminus } \{b_{s,t,v},u\}. \end{aligned}$$

There are two cases to consider (b1) $v \in V(\pi (b_{s,t,v},w))$, in such a case, $v \notin V(\pi (w,u))$ and hence $\pi (w,u)=SP(w,u, G {\setminus } \{v\},W)=P_{s,t,v}[w,u]$, contradicting the fact that $\mathtt{LastE}(P_{s,t,v}[s,u]) \notin T_0(S)$. (b2) $v \in V(\pi (w,u))$. In such a case, $v \notin V(\pi (b_{s,t,v},w))$ and hence $\pi (b_{s,t,v},w)=SP(b_{s,t,v},w, G {\setminus } \{v\},W)= P_{s,t,v}[b_{s,t,v},w]$, contradicting the fact that $b_{s,t,v}$ is a divergence point from $\pi (s,t)$. The lemma holds. $\square$

The next lemma shows that a new-ending $P_{s,t,v}$ path whose last edge is not in $G_0$ (see Eq. (2)), protecting against faults in the near segment, has a good approximate replacement path $\widetilde{P}_{s,t,v}$ in $G_0$.

Lemma 3

If $\mathtt{LastE}(P_{s,t,v}) \notin G_0$ and $v \in V^{\mathtt{near}}(s,t)$, then $\mathrm{dist}(s,t, G_0 {\setminus } \{v\})\le \mathrm{dist}(s,t, G{\setminus } \{v\})+4$.

Proof

Since $v \in V^{\mathtt{near}}(s,t)$, i.e., the failing vertex occurs strictly below $\mathtt{LCA}(s, C_1(t))$ on $\pi (s,t)$, there exists a vertex $w \in C_1(t)$ such that $v \notin V(\pi (s,w))$ (hence in particular $w \ne v$). See Fig. 1. Since $\mathtt{LastE}(P_{s,t,v}) \notin E^{\mathtt{local}}$, it holds that $v \ne z_1(t)$. Consider the following $s-t$ path $P=\pi (s,w) \circ [w, z_1(t),t]$. Clearly, $P \subseteq (T_0(S) \cup G_{\varDelta }) {\setminus } \{v\}$. By the triangle inequality, as the diameter of the cluster $C_1(t)$ is 2, it holds that

$$\begin{aligned} \mathrm{dist}(s,t, (T_0(S) \cup G_{\varDelta }) {\setminus } \{v\})\le & {} \mathrm{dist}(s,w,G)+2 \\ \le \mathrm{dist}(s,t,G)+4\le & {} \mathrm{dist}(s,t,G {\setminus } \{v\})+4. \end{aligned}$$

The lemma follows. $\square$

Fig. 1

Handling near vertex faults. Schematic illustration of an approximate replacement path in $(T_0 \cup G_\varDelta ){\setminus } \{v\}$. Shown is an $\pi (s,t)$ whose failing vertex v occurs strictly below the least common ancestor $\mathtt{LCA}(s, C_1(t))$. The alternative replacement path exploits the surviving $\pi (s,w) \subseteq T_0(S)$ path for $w \in C_1(t)$ and the intracluster path connecting w and v through $z=z_v(t)$

The following auxiliary lemma is useful. It considers a new-ending path $P_{s,t,v}$ where $D^-_{s,t,v}=D_{s,t,v} {\setminus } \{b_{s,t,v}\}$ and (x, y) is the first missing edge in $P_{s,t,v} {\setminus } G_0$ (where x is closer to s).

Lemma 4

For every vertex $u \in P_{s,t,v}$ such that $\mathtt{LastE}(P_{s,t,v}[s,u]) \notin G_0$, it holds that: (a) $C_v(u)=C_1(u)$. (b) $P_{s,t,v}[x, t] \subseteq D^-_{s,t,v}$.

Proof

Begin with (a). By the definition of the weight assignment W, it holds that $P_{s,t,v}[s,u]=P_{s,u,v}=SP(s,u, G {\setminus } \{v\},W)$. Since $\mathtt{LastE}(P_{s,t,v}[s,u]) \notin E^{\mathtt{local}}$, it holds that $v \ne z_1(u)$, concluding that $z_v(u)=z_1(u)$ and hence $C_v(u)=C_1(u)$. Claim (a) follows. Consider claim (b). Let $b=b_{s,t,v}$. We show that $x \ne b$, which implies the claim. By Lemma 2, $v \in V(\pi (s,y))$. Since b appears above v on $\pi (s,t)$, b is a common vertex in both $\pi (s,t)$ and $\pi (s,y)$. Hence, the $s-y$ shortest path has the following form: $\pi (s, y)=\pi (s,b) \circ \pi (b,v) \circ \pi (v,y)$. Since $b \ne v \ne y$, $\mathrm{dist}(b, y,G)\ge 2$, and hence also $\mathrm{dist}(b, y,G{\setminus }\{v\})\ge 2$, concluding that $b \ne x$. The lemma follows. $\square$

Corollary 1

Let $t \in V_{C}$. For every $P_{s,t,v} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$, $P_{s,t,v}[x,t] \cap V_{f}(C_v(t))=\emptyset$ where x is the first vertex of $D^-_{s,t,v}$.

Proof

Since $P_{s,t,v}$ is independent, by Eq. 1, $D^-_{s,t,v} \cap T(t,S)=\{t\}$. Since $t \in C_v(t)$, by Eq. (3), $t \notin V_{f}(C_v(t))$ and hence $D^-_{s,t,v} \cap V_{f}(C_v(t))=\emptyset$. The corollary follows Lemma 4(b). $\square$

Correctness analysis of $H_4(S)$ We now show that $H_4(S)$ is a $(4,S)$ FT-spanner.

Lemma 5

$H_4(S)$ is a $(4,S)$ FT-spanner.

Proof

Fix a source $s \in S$ and let $H=H_4(S)$. We then show that for every pair $(t,v) \in V \times V$ it holds that

$$\begin{aligned} \mathrm{dist}(s,t,H {\setminus } \{v\})\le \mathrm{dist}(s,t,G {\setminus } \{v\})+4. \end{aligned}$$

(5)

To show this, define $e_{t,v}$ to be the last edge of $P_{s,t,v}=SP(s,t, G {\setminus } \{v\},W)$ that is missing in H and let $d(t,v)=\mathrm{dist}(s,e_{t,v},P_{s,t,v})$ be the distance of $e_{t,v}$ from $s$ on $P_{s,t,v}$, for every pair $(t,v) \in V \times V$. The proof is shown by induction on d(t, v). For $d(t,v)=0$, $P_{s,t,v} \subseteq H$ and Eq. (5) holds vacuously. Assume that the claim holds for all (t, v) pairs with $d(t,v)\le d-1$ and consider some pair $(t_0,v_0)$ pair with $d(t_0,v_0)= d$. Let $e_{t_0,v_0}=(u,t')$ be the last missing edge on $P_{s,t_0,v_0}$. We distinguish between two cases.

Case (1) $d(t',v_0)\le d-1$ Let $P'' \in SP(s, t', H {\setminus } \{v_0\})$. By induction assumption, it holds that

$$\begin{aligned} |P''|\le & {} \mathrm{dist}(s, t', G {\setminus } \{v_0\})+4\\= & {} |P_{s,t_0, v_0}[s, t']|+4. \nonumber \end{aligned}$$

(6)

We now consider the following $s-t_0$ replacement path $Q=P'' \circ P_{s,t_0, v_0}[t',t_0]$. By definition of $(t',v_0)$ (last missing edge on $P_{s,t',v_0}$), $Q \subseteq H {\setminus } \{v_0\}$. In addition,

$$\begin{aligned} |Q|= & {} |P''|+|P_{t_0, v_0}[t',t_0]|\\\le & {} |P_{s,t_0, v_0}[s, t']|+4+|P_{s,t_0, v_0}[t', t_0]|\\= & {} |P_{s,t_0, v_0}|+4 ~=~ \mathrm{dist}(s, t_0, G {\setminus } \{v_0\})+4, \end{aligned}$$

where the inequality follows by Eq. (6), and Eq. (5) holds as required.

Case (2) $d(t',v_0)\ge d$ In this case, since $|P_{s,t',v_0}|=|P_{s,t_0,v_0}|$, $d(t',v_0)=d$. Hence, the last edge of $P_{s,t',v_0}$ is not in H. Since $\pi (s, t') \subseteq H$, we have that the failing vertex $v_0$ occurs on the shortest-path $\pi (s, t')$. Since the last edge of $P_{s,t',v_0}=P_{s,t_0,v_0}[s,t']$ is missing in H, by the fact that the clustering graph $G_{\varDelta }$ is in H, by Observation 5(1), it holds that $t'$ is a clustered vertex. By step (2), since $E^{\mathtt{local}} \subseteq H$, it holds that $v_0 \notin \{z_1(t'), \mathtt{LCA}(s,C_1(t'))\}$. Combining with Lemma 3, it holds that $v_0 \notin V^{\mathtt{near}}(s,t')$. Hence, $v_0 \in V^{\mathtt{far}}(s,t')$. We next claim that $P_{s,t',v_0}$ is an independent path. This holds since the last edges of $t_0$’s dependant replacement paths $E^{\mathtt{far}}_{\mathtt{dep}}(t_0)$ were added to H in step (4.1). Thus $P_{s,t',v_0}$ is an independent path and hence it was considered to be bought in the path-buying procedure of Step (4.2). If the algorithm bought $P_{s, t', v_0}$, Eq. (5) holds. So, it remains to consider the case where the algorithm did not buy this path. Let $\tau$ be the iteration at which $P_{\tau }=P_{s, t', v_0}$ was considered to be purchased in the path-buying procedure. Let $G_\tau$ be the current spanner in iteration $\tau$. Let x be the vertex incident to the first missing edge on $P_{\tau } {\setminus } E(G_{\tau })$.

Let $C_0=C_{v_0}(t')$ be the cluster of $t'$ in $G_\varDelta {\setminus } \{v_0\}$. Since $\mathtt{LastE}(P_{\tau }) \notin E^{\mathtt{local}}$, by Lemma 4(a) $C_0=C_1(t')$ and $z_{v_0}(t')=z_1(t')$. By definition,

$$\begin{aligned} v_0 \in V^{\mathtt{far}}(s,t')=\pi (s, C_0){\setminus } \{\mathtt{LCA}(s,C_0)\}. \end{aligned}$$

Hence, the failing vertex is not in the cluster $C_0$, i.e., $v_0 \notin C_0$ and by Eq. (3),

$$\begin{aligned} v_0 \in V_{f}(C_0). \end{aligned}$$

(7)

Since $P_{\tau }$ was not bought by the algorithm, by Eq. (4), we have that

$$\begin{aligned} \mathrm{dist}(C_{v_0}(x), C_0, G_\tau {\setminus } V_{f}(C_0))\le \mathrm{dist}(x, t', P_\tau ). \end{aligned}$$

(8)

Let $w_1 \in C_{v_0}(x)$ and $w_2 \in C_0$ be an arbitrary closest pair in $G_\tau {\setminus } V_{f}(C_0)$ from the clusters $C_{v_0}(x)$ and $C_0$ respectively satisfying that $\mathrm{dist}(w_1, w_2, G_\tau {\setminus } V_{f}(C_0))=\mathrm{dist}(C_{v_0}(x), C_0, G_\tau {\setminus } V_{f}(C_0))$.

Let $z_1$ (resp., $z_2$) be the cluster center of $C_{v_0}(x)$ (resp., $C_0$). Consider the following $s-t'$ replacement path in $H{\setminus } \{v_0\}$, $P_5=P_1 \circ P_2 \circ P_3 \circ P_4$ where $P_1=P_\tau [s, x]$, $P_2=[x, z_1, w_1]$ and $P_3 \in SP(w_1, w_2, G_\tau {\setminus } V_{f}(C_0))$ and $P_4=[w_2, z_2, t']$. For an illustration see Fig. 2. We first claim that $P_5 \subseteq H {\setminus } \{v_0\}$. Since x is incident to the first missing edge on $P_{\tau }$, $P_1$ is in $H {\setminus } \{v_0\}$. By Eq. (7), $v_0 \in V_f(C_0)$ and since $w_1,w_2\subseteq G_\tau {\setminus } V_{f}(C_0)$ it also holds that $w_1,w_2 \ne v_0$. Finally note that $G_{\tau },G_{\varDelta } \subseteq H$, hence $P_2,P_4 \subseteq H {\setminus } \{v_0\}$. We next bound the length of $P_5$.

$$\begin{aligned}&\mathrm{dist}(s, t', H {\setminus } \{v_0\})\le |P_5| ~\le ~ \mathrm{dist}(s, x, G {\setminus } \{v_0\})\nonumber \\&\quad +\, 2+\mathrm{dist}(w_1, w_2, G_\tau {\setminus } V_{f}(C_0))\nonumber \\&\quad + \, 2=\mathrm{dist}(s, x, G {\setminus } \{v_0\})\nonumber \\&\quad +\mathrm{dist}(C_{v_0}(x), C_0, G_\tau {\setminus } V_{f}(C_0))+4 \nonumber \\&\quad \le \mathrm{dist}(s, x, G {\setminus } \{v_0\})+\mathrm{dist}(x, t', P_\tau )+4 \nonumber \\&\quad = |P_{s,t',v}|+4=\mathrm{dist}(s, t', G {\setminus } \{v_0\})+4, \end{aligned}$$

(9)

where Eq. (9) follows by Eq. (8). Equation (5) holds for the pair $(t', v_0)$, and hence also for the pair $(t', v_0)$ (as $(u,t')$ is the last missing edge on $P_{s,t_0,v_0}$. The claim holds. $\square$

Fig. 2

Schematic illustration of the path-buying procedure of Alg. Cons4SWSpanner. Shown is an $s-t$ path $P_{\tau }=P_{s,t_i,v_0}$ considered to be bought in time $\tau$. The green paths correspond to shortest-paths in $T_0(s)$ and the red edges correspond to missing edges on $P_{\tau } {\setminus } E(G_{\tau })$. The first missing edge on $P_{\tau } {\setminus } E(G_{\tau })$ is incident to x. If $P_{\tau }$ was not bought, then there exists a short route between a pair of vertices $w_1$ and $w_2$ belonging to $C_{v_0}(x)$ and $C_{v_0}(t_i)$ (respectively) in $H {\setminus } \{v_0\}$ (color figure online)

Size analysis of $H_4(S)$ We proceed with the size analysis. Consider Step (3). Since $E^{\mathtt{local}}(t)$ includes for every source $s \in S$ at most two last edges of the $s-t$ replacement-paths protecting against the failing of $z_1(t)$ and $\mathtt{LCA}(s,C_1(t))$, it holds that

Observation 9

For every $t \in V_{C}$, $|E^{\mathtt{local}}(t)|=O(|S|)$, hence $|E^{\mathtt{local}}|=O(|S| \cdot n)$.

Bounding the number of last edges in $E^{\mathtt{far}}_{\mathtt{dep}}(t)$. We now turn to bound the number of edges added due to step (4.1), i.e., the last edges of new-ending dependent paths $P_{s,t,v}$ protecting against the faults in the far segment $\pi ^{\mathtt{far}}(s,t)$. To bound the number of edges in $E^{\mathtt{far}}_{\mathtt{dep}}(t)$, consider the partial BFS tree rooted at t, $T(t,S)\subseteq T_0(t)$, whose leaf set is contained in the vertex set $S$ where $T(t,S)=\bigcup _{s\in S} \pi (s,t)$. It is convenient to view this tree as going from the leafs towards the root, where the root t is at the bottom and the leafs are on the top of the tree. Let $V^+=S\cup \{u \in T(t,S) ~\mid ~ \mathtt{deg}(u, T(t,S))\ge 3\},$ be the union of $S$ and the vertices with degree at least 3 in the tree $T(t,S)$. We have that $|V^+| <2|S|$. A pair of vertices $x, y \in V^+$ is adjacent if their shortest-path $\pi (x,y)$ is contained in the tree $T(t,S)$ and it is free from any other $V^+$ vertex, i.e, $\pi (x,y) \subseteq T(t,S)$ and $\pi (x,y) \cap V^+=\{x,y\}$. Let $\Pi (V^+)=\{\pi (x,y) ~\mid ~ x, y \in V^+ \text{ and } x, y \text{ are } \text{ adjacent } \}$ be the collection of paths between adjacent pairs.

Observation 10

(1) $T(t,S)=\Pi (V^+)$. (2) $\Pi (V^+)$ consists of at most $2|S|+1$ paths $\pi (x,y)$ (i.e., there are at most $2|S|+1$ adjacent pairs).

To bound $|E^{\mathtt{far}}_{\mathtt{dep}}(t)|$, we first claim that every two dependent replacement paths with the same divergence point have the same last edge.

Lemma 6

For every two dependent paths $P_{s_1,t, v_1}, P_{s_2,t, v_2} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$, if $b_{s_1,t, v_1} = b_{s_2,t, v_2}$ then $\mathtt{LastE}(P_{s_1,t, v_1}) =\mathtt{LastE}(P_{s_1,t, v_2})$.

Proof

Let $b=b_{s_1,t,v_1}=b_{s_2,t,v_2}$. Since $b \in V(\pi (s_1,t)) \cap V(\pi (s_2,t))$ it holds that $\pi (s_i,t)=\pi (s_i, b) \circ \pi (b,t)$ for $i \in \{1,2\}$. In addition, since $P_{s_i,t, v_i}[s_i,b]=\pi (s_i,b)$ for $i \in \{1,2\}$, it holds that both failing vertices $v_1$ and $v_2$ occur in the common segment $\pi (b,t)$. Recall that $P_{s_i,t, v_i}$ is a new-ending path, hence by the definition of the divergence point b (see Lemma 2(b)), it holds that $V(P_{s_i,t,v_i}[b,t]) \cap V(\pi (b,t))=\{b,t\}$ and hence both detours are free from the failing vertices. Hence, $P_{s_1,t, v_1}[b,t]=P_{s_2,t, v_2}[b,t]=SP(b,t, G {\setminus }\{v_1,v_2\},W)$. We get that $\mathtt{LastE}(P_{s_1,t, v_1}) =\mathtt{LastE}(P_{s_2,t, v_2})$ as needed. $\square$

Since our goal is to bound the number of last edges of the new ending dependent paths ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$, to avoid double counting, we now restrict attention to ${\mathcal {Q}}^{\mathtt{far}}(t)$, a collection of representative paths in ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$ each ending with a distinct new edge from $E^{\mathtt{far}}_{\mathtt{dep}}(t)$. Formally, for each new edge $e \in E^{\mathtt{far}}_{\mathtt{dep}}(t)$, let P(e) be an arbitrary path in ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$ satisfying that $\mathtt{LastE}(P(e))=e$. Let ${\mathcal {Q}}^{\mathtt{far}}(t)=\{P(e), e \in E^{\mathtt{far}}_{\mathtt{dep}}(t)\}$ (hence $|{\mathcal {Q}}^{\mathtt{far}}(t)|=|E^{\mathtt{far}}_{\mathtt{dep}}(t)|$). From now on, we aim towards bounding the cardinality of ${\mathcal {Q}}^{\mathtt{far}}(t)$. Let $\mathtt{DP}=\{b_{s,t,v} ~\mid ~ P_{s,t,v} \in {\mathcal {Q}}^{\mathtt{far}}(t)\}$ be the set of divergence points of the new ending paths in ${\mathcal {Q}}^{\mathtt{far}}(t)$. By Lemma 6, it holds that in order to bound the cardinality of ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{dep}}(t)$, it is sufficient to bound the number of distinct divergence points. To do that, we show that every path $\pi (x,y)$ of two adjacent vertices $x,y \in V^+$, contains at most one divergence point in $\mathtt{DP}{\setminus } V^+$.

Lemma 7

$|\pi (x,y) \cap (\mathtt{DP}{\setminus } V^+)| \le 1$ for every $\pi (x,y) \in \Pi (V^+)$.

Fig. 3

Schematic illustration of new-ending dependent paths. Shown is the tree T(t, S) with the root t at the bottom and leaf set is contained in the set of sources S. a The two replacement paths have the same divergence point b, hence one of the new last edges is redundant. b A new-ending $s_1-t$ dependant path $P_{s_1,t,v_1}$ with a divergence point $b_1 \in V(\pi (x,y))$ intersects with $\pi (s_3,t)$ at the vertex $w \notin \{b_1,t\}$. Since $P_{s_1,t,v}$ is a new-ending path (i.e., its last edges is not on T(t, S)), the failing vertex v must occur on the path $\pi (w,t)$. Hence $v_1\in V(\pi (s_1,t)) \cap V(\pi (s_3,t))$, implying that $v_1\in V(\pi (y,t))$. Since this holds for any new-ending path with a divergence point in $\pi (x,y)$, we get that only one new edge from all these paths is needed

Proof

Assume, towards contradiction, that there are two divergence points $b_{s_1,t,v_1}$ and $b_{s_2,t,v_2}$ on some path $\pi (x,y)$ for two adjacent vertices $x,y \in V^+$. For ease of notation, let $P_i=P_{s_i,t,v_i}, b_i=b_{s_i,t,v_i}$, $D_i=D_{s_i,t,v_i}$ and $D^-_i=D_i {\setminus } \{b_i\}$ for $i \in \{1,2\}$. Without loss of generality, assume the following: (1) y is closer to t than x and (2) $b_{2}$ is closer to t than $b_{1}$. By construction, the vertices $s_1$ and $s_2$ are in the subtree $T(x) \subseteq T(t,S)$. For an illustration see Fig. 3. We now claim that the failing vertices $v_1,v_2$ occur in the interior of $\pi (y, t)$. Since $D^-_1$ and $D^-_2$ are vertex disjoint with $\pi (y,t){\setminus } \{t\}$, it would imply that both detour segments $D_1$ and $D_2$ are free from the failing vertices and hence at least one of the two new edges $\mathtt{LastE}(P_1), \mathtt{LastE}(P_2)$ could have been avoided. We now focus on $v_1$ and show that $v_1 \in V(\pi (y,t))$, the exact same argumentation holds for $v_2$. Since $P_{1}$ is a new-ending dependent path, by Eq. (1), there exists some source $s_3 \in S {\setminus } \{s_1\}$ satisfying that $\left( D^-_1 \cap \pi (s_3, t)\right) {\setminus }\{t\} \ne \emptyset$. Let $w \in \left( V(D^-_1) \cap V(\pi (s_3, t))\right) {\setminus }\{t\}$ be the first intersection point (closest to $s_1$). See Fig. 3 for schematic illustration. We first claim that $s_3$ is not in T(x) where T(x) is the subtree of $T(t,S)$ rooted at x. To see why this holds, assume, towards contradiction, that $s_3 \in T(x)$. It then holds that the replacement path $P_1$ has the following form $P_1=\pi [s_1, x] \circ \pi (x, b_{1}) \circ P_1[b_{1}, w] \circ P_1[w, t]$. Recall, that since $b_{1} \in \mathtt{DP}{\setminus } V^+$, $b_{1} \ne x$ and also $b_1\ne w$. Since $P_1[x,w]$ goes through $b_1$, by the optimality of $P_1$, it holds that

$$\begin{aligned} \mathrm{dist}(x,w,G {\setminus } \{v_1\})>\mathrm{dist}(b_1,w,G {\setminus } \{v_1\}). \end{aligned}$$

(10)

On the other hand, the path $\pi (s_3, t)$ has the following form: $\pi (s_3,t)=\pi (s_3,w) \circ \pi (w,x) \circ \pi (x,b_1)\circ \pi (b_1,t)$. Hence, $\pi (w,b_1)$ goes through x. Since the failing vertex $v_1 \in V(\pi (b_1,t))$ is not in $\pi (w,b_1)$, by the optimality of $\pi (w,b_1)$, we get that $\mathrm{dist}(w,b_1,G {\setminus } \{v_1\})>\mathrm{dist}(x,w,G {\setminus } \{v_1\})$, leading to contradiction with in Eq. (10). Hence, we conclude that $s_3 \notin T(x)$ (in particular this implies that $s_3 \ne s_2$). Note that $\pi (w,t)$ is a segment of $\pi (s_3,t)$ and hence it is contained in the tree $T(t,S)$. Since $P_1$ is a new-ending path (i.e., $\mathtt{LastE}(P_1) \notin T(t,S)$), we have that $P_{1}[w,t]\ne \pi (w,t)$ are distinct $w-t$ paths. We next claim that the failing vertex $v_1$ must occur on $\pi (w,t)$ and hence also on $\pi (s_3,t)$. To see this, observe that if $\pi (w,t)$ would have been free from the failing vertex $v_1$, then it implies that $\pi (w,t)=SP(w,t, G {\setminus } \{v_1\},W)=P_1[w,t]$, contradiction as $\mathtt{LastE}(P_1) \ne \mathtt{LastE}(\pi (w,t))$. Finally, we show that $v_1 \in V(\pi (y,t))$. By the above, the failing vertex $v_1$ is common to both paths $\pi (s_1,t)$ and $\pi (s_3,t)$, i.e., $v_1 \in V(\pi (s_1,t)) \cap V(\pi (s_3,t))$. By the definition of the path $\pi (x,y)$, all its internal vertices u have degree 2 and hence $(V(\pi (x,y)) \cap V(\pi (s_3,t))) {\setminus } \{y\}=\emptyset$, concluding that $v_1 \in V(\pi (y, t))$. By the same argumentation, it also holds that $v_2$ is in $\pi (y,t)$. As the detours $D_{1}$ and $D_{2}$ are vertex disjoint with $\pi (y,t) {\setminus } \{t\}$, it holds that they are free from the two failing vertices, i.e., $v_1,v_2 \notin D_{1} \cup D_{2}$. Since $P_1,P_2 \in {\mathcal {Q}}^{\mathtt{far}}(t)$, it holds that $\mathtt{LastE}(P_{1}) \ne \mathtt{LastE}(P_{2})$, and hence there are two $b_{1}-t$ distinct shortest paths in $G {\setminus } \{v_1, v_2\}$, given by $D_{1}$ and $\pi (b_1,b_2) \circ D_{2}$. By optimality of these paths, they are of the same lengths. Again, we end with contradiction to the uniqueness of the weight assignment W. The claim follows. $\square$

We now are now ready to bound $|E^{\mathtt{far}}_{\mathtt{dep}}(t)|$.

Lemma 8

For every $t \in V_{C}$, $|E^{\mathtt{far}}_{\mathtt{dep}}(t)|=O(|S|)$.

Proof

By Lemma 6 there are at most $|V^+|$ replacement paths with divergence point in $V^+$. By Lemma 7, there is at most one divergence point on each segment $\pi (x,y)$ of an adjacent pair (x, y). Note that the divergence points $\mathtt{DP}$ are in the tree T(t, S) and that the internal segments of $\pi (x,y), \pi (x',y')$ for $x,x',y,y' \in V^+$ are vertex disjoint. Combining with Observation 10(2), we get $|E^{\mathtt{far}}(t)|=|{\mathcal {Q}}^{\mathtt{far}}(t)|=O(|S|)$. The lemma follows. $\square$

We complete the size analysis and prove Theorem 8, by bounding the number of edges added by the path-buying procedure of Step (4.2).

Bounding the number of edges added due to the path-buying procedure Finally, it remains to bound the number of edges added due to the path-buying procedure of step (4.2). Let ${\mathcal {B}} \subseteq {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$ be the set of paths bought in the path-buying procedure of Step (4.2). For every ordered pair of clusters $C_1, C_2 \in {\mathcal {C}}$, let ${\mathcal {B}}(C_1, C_2) \subseteq {\mathcal {B}}$ be the set of paths that were added since they improved the distance of $C_1$ and $C_2$, that is

$$\begin{aligned} {\mathcal {B}}(C_1, C_2)=\{ P_{\tau } \in {\mathcal {B}} ~\mid ~ C_{1,\tau }=C_1 \text{ and } C_{2,\tau }=C_2\} \end{aligned}$$

Clearly, ${\mathcal {B}}=\bigcup _{C_1, C_2 \in {\mathcal {C}}} {\mathcal {B}}(C_1, C_2)$. We next use the fact that the diameter of each cluster $C \in {\mathcal {C}}$ is small, to bound the cardinality of the set ${\mathcal {B}}(C_1, C_2)$.

Lemma 9

$|{\mathcal {B}}(C_1, C_2)| \le 5$ for every $C_1, C_2 \in {\mathcal {C}}$.

Proof

Fix $C_1, C_2 \in {\mathcal {C}}$ and order the paths of ${\mathcal {B}}(C_1, C_2)$ according to the time step they were added to the spanner ${\mathcal {B}}(C_1, C_2)=\{P_{\tau _1}, \ldots , P_{\tau _N}\}$ and $\tau _1 < \tau _2 < \cdots < \tau _N$ where $N=|{\mathcal {B}}(C_1, C_2)|$. Since $P_{\tau _k} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$, it is a new-ending path, i.e., $\mathtt{LastE}(P_{\tau _k}) \notin G_0$. Let $P_{\tau _k}=P_{s_k,t_k,v_k}$ and $D_{\tau _k}=D_{s_k,t_k,v_k}$ denote the detour segment of this path. Hence, each $P_{\tau _k}$ protects against the failing of $v_k$. Let $x_k$ be the vertex adjacent to the first missing edge on $P_{\tau _k}$. Hence, $C_1=C_{v_k}(x_k)$ and $C_2=C_{v_k}(t_k)$ for every $k \in \{1, \ldots , N\}$ and also $V_{f}(C_{v_k}(t_k))=V_{f}(C_2)$ for every $k \in \{1,\ldots , N\}$. Since $T_0(S) \subseteq G_0$, the missing edges of $P_{\tau _k}$ are restricted to the detour segment $D_{\tau _k}$.

In addition, since $P_{\tau _k} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$, it holds that the failing vertex $v_k$ occurs on the far segment $\pi ^{\mathtt{far}}(s_k,t_k)$ and in particular, $v_k \notin C_2$ (i.e., $v_k$ occurs strictly above the least common ancestor $\mathtt{LCA}(s_k, C_2)$ and since all cluster members appear on $T_0(s_k)$ in the subtree rooted at $\mathtt{LCA}(s_k,C_2)$, the far segment $\pi ^{\mathtt{far}}(s_k,t_k)$ is free from cluster members). We therefore have

$$\begin{aligned} \{v_1, \ldots , v_N\}\subseteq V_f(C_2). \end{aligned}$$

(11)

Note that each path $P_{\tau _k}$ protects against the failing of the single vertex $v_k$, however, since each $P_{\tau _k}$ belongs to ${\mathcal {B}}(C_1, C_2)$, Eq. (11) holds.

Note that $\pi (s_k, C_2) \subseteq \pi (s_k,t_k)$ and hence it is contained in $T(t_k,S)$ for every $k \in \{1,\ldots ,N\}$. By the definition of independent paths (see Eq. (1) for the definition of dependent paths), we have that

$$\begin{aligned} D^-_{s_k,t_k,v_k} \cap T(t_k,S)=\{t_k\}. \end{aligned}$$

(12)

Consequently, by Lemma 4(b),

$$\begin{aligned} P_{\tau _k}[x_k,t_k] \subseteq D^-_{\tau _k} \subseteq G {\setminus } V_{f}(C_2). \end{aligned}$$

(13)

where the last inclusion holds by the fact that $t_k \notin V_{f}(C_2)$ and $V_{f}(C_2) \subseteq \bigcup _{s \in S} \pi (s, C_2) \subseteq \bigcup _{s \in S} \pi (s, t_k)=T(t_k,S)$. Let $z_i \in Z$ be the cluster center of $C_i$ for $i \in \{1,2\}$. We therefore have that $z_1=z_{v_1}(x_1) =\cdots =z_{v_N}(x_N)$ and $z_2=z_{v_1}(t_1)=\cdots =z_{v_N}(t_N)$ and hence $z_2 \ne v_k$ for every $k \in \{1, \ldots , N\}$. Hence,

$$\begin{aligned} z_1,z_2 \notin \{v_1, \ldots , v_N\}. \end{aligned}$$

(14)

For every $k \in \{1,\ldots , N\}$, denote

$$\begin{aligned} X_k=\mathrm{dist}(x_k, t_k, G_{\tau _{k+1}} {\setminus } V_{f}(C_2)). \end{aligned}$$

We now show that $X_k<X_{k-1}$ for every $k \in \{2, \ldots N\}$.

Since the path $P_{\tau _k}$ is purchased at time $\tau _k$, we have that

$$\begin{aligned} X_k\le & {} \mathrm{dist}(x_k, t_k, P_{\tau _k} {\setminus } V_{f}(C_2)) \end{aligned}$$

(15)

$$\begin{aligned}= & {} \mathrm{dist}(x_k, t_k, P_{\tau _k}) \end{aligned}$$

(16)

$$\begin{aligned}< & {} \mathrm{dist}(C_{1}, C_{2}, G_{\tau _{k}} {\setminus } V_{f}(C_2)) \end{aligned}$$

(17)

$$\begin{aligned}\le & {} X_{k-1}, \end{aligned}$$

(18)

where Eq. (15) follows by the fact that $P_{\tau _k} \subseteq G_{\tau _{k+1}}$, Eq. (16) follows by Eq. (13). Equation (17) follows by the fact that $P_{\tau _k}$ was bought and by Eq. (4), and Eq. (18) follows by the fact that $x_{k-1} \in C_1$ and $t_{k-1} \in C_2$.

Therefore, we have that

$$\begin{aligned} X_N \le X_1-(N-1). \end{aligned}$$

(19)

Conversely, we have that

$$\begin{aligned} X_N\ge & {} \mathrm{dist}(x_{N}, t_N, G {\setminus } \{v_1, \ldots , v_N\}) \end{aligned}$$

(20)

$$\begin{aligned}\ge & {} \mathrm{dist}(x_1, t_1, G {\setminus } \{v_1, \ldots , v_N\})-4 \end{aligned}$$

(21)

$$\begin{aligned}= & {} \mathrm{dist}(x_1, t_1, P_{\tau _1})-4 = \mathrm{dist}(x_1, t_1, P_{\tau _1} {\setminus } V_{f}(C_2))-4 \nonumber \\\end{aligned}$$

(22)

$$\begin{aligned}\ge & {} X_1-4, \end{aligned}$$

(23)

where Eq. (20) follows as $G_{\tau _{N+1}} \subseteq G$ and by Eq. (11), $\{v_1, \ldots , v_N\} \subseteq V_{f}(C_2)$. To see Eq. (21), we need to prove the existence of the intracluster paths $R_1=[x_1, z_1, x_N]$ and $R_2=[t_1, z_2, t_N]$ in $G {\setminus } \{v_1, \ldots , v_N\}$ where $z_1$ (resp., $z_2$) is the cluster center of $C_1$ (resp., $C_2$). By definition, $x_{1},x_N \in C_{1}$ and $t_1,t_N \in C_{2}$. Hence, $z_1$ (resp., $z_2$) is a common neighbor of both $x_{1}$ and $x_N$ (resp., $t_1$ and $t_N$). By (14), $z_1,z_2 \notin \{v_1, \ldots , v_N\}$.

In addition, by Eq. (13), $x_k, t_k \in G {\setminus } V_{f}(C_2)$ for every $k\in \{1, \ldots , N\}$ and by Eq. (11), it also holds that $x_k,t_k \notin \{v_1, \ldots , v_N\}$ for every $k \in \{1,\ldots ,N\}$. Hence, $R_1$ and $R_2$ exist in $G{\setminus } \{v_{1},\ldots ,v_N\}$ and Eq. (21) follows by the triangle inequality. Equation (22) follows by Eqs. (13) and (11). Finally, Eq. (23) follows by the fact that $P_{\tau _1}$ was added at step $\tau _1$, hence $P_{\tau _1} \subseteq G_{\tau _{2}}$. We get that $N \le 5$. Lemma 9 follows. $\square$

We are now ready to bound the number of edges added in the path-buying phase.

Lemma 10

$|H_4(S){\setminus } G_0|=O((n/|S|)^3)$.

Proof

By Observation 5(2) and Observation 6, every path $P_{\tau _k}$ contains at most $O(n/\varDelta )$ edges in $G {\setminus } G_{\varDelta }$. Hence,

$$\begin{aligned} |E(G_{\tau '} {\setminus } G_0)|= & {} O(n/\varDelta ) \cdot |{\mathcal {B}}|\end{aligned}$$

(24)

$$\begin{aligned}= & {} O(n/\varDelta ) \cdot \sum _{C_1, C_2 \in {\mathcal {C}}} |{\mathcal {B}}(C_1, C_2)|\end{aligned}$$

(25)

$$\begin{aligned}\le & {} O(n/\varDelta )\cdot |{\mathcal {C}}|^2=O((n/\varDelta )^3). \end{aligned}$$

(26)

where the last equality follows by the fact that $|{\mathcal {C}}|=O(n/\varDelta )$. Taking $\varDelta =|S|$ establishes the lemma. $\square$

Theorem 8 follows by Observation 9, the properties of the clustering graph (Observation 5(4)), Lemma 5 and Lemma 10.

4.2 Sourcewise spanner with additive stretch 8

In this section, we present Alg. Cons8SWSpanner for constructing a sourcewise additive FT-spanner with additive stretch 8. The size of the resulting spanner is smaller (in order) than the $H_4(S)$ spanner of Alg. Cons4SWSpanner, at the expense of larger stretch. The algorithm is similar in spirit to Alg. Cons4SWSpanner and the major distinction is in the path-buying procedure of step (4.2).

Lemma 11

There exists a subgraph $H_{8}(S) \subseteq G$ with $O(|S| \cdot n+(n/|S|)^{2})$ edges s.t. $\mathrm{dist}(s,t, H_{8}(S) {\setminus } \{v\})\le \mathrm{dist}(s,t, G {\setminus } \{v\})+8$ for every $(s, t) \in S \times V$ and every $v \in V$.

4.2.1 Algorithm Cons8SWSpanner for constructing $H_8(S)$ spanner

Step (0–4.1) Same as in Alg. Cons4SWSpanner. Let $E^{\mathtt{local}}, E^{\mathtt{far}}_{\mathtt{dep}}$ be the set of last edges obtained at the end of step (3) and set (4.1) respectively. Let ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$ be the set of new-ending independent paths.

Step (4.2): Handling independent new-ending paths Starting with $G_0$ as in Eq. (2), the paths of ${\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$ are considered in an arbitrary order. At step $\tau$, we are given $G_\tau \subseteq G$ and consider the path $P_{\tau }=P_{s,t,v}$. Let $D_\tau =P_\tau {\setminus } \pi (s,t)$ be the detour segment of $P_{\tau }$ (since $\pi (s,t) \subseteq T_0(S)$ is in $G_0$, all missing edges of $P_{\tau }$ occur on its detour segment).

To decide whether $P_{\tau }$ should be added to $G_\tau$, the number of pairwise cluster “distance improvements” is compared to the number of new edges added due to $P_{\tau }$. To do that we compute the set $\mathtt{ValSet}(P_{\tau })$ containing all pairs of clusters that achieves a better distance if $P_{\tau }$ is bought. The value and cost of $P_{\tau }$ are computed as follows. Let $\mathtt{Val}(P_{\tau })=|\mathtt{ValSet}(P_{\tau })|$ be the number of distance improvements as formally defined later. We next define a key vertex $\phi _\tau \in V_{C}$ on the path $P_{\tau }$.

Definition 3

Let $\phi _{s,t,v}$ (or $\phi _{\tau }$ for short) be the last vertex on $P_{\tau }$ (closest to t) satisfying that: (N1) $\mathtt{LastE}(P_{\tau }[s, \phi _{\tau }]) \notin G_{\tau }$, and (N2) $v \in V^{\mathtt{near}}(s,\phi _\tau )=\pi (\ell , \phi _{\tau }){\setminus } \{\ell \}$ where $\ell =\mathtt{LCA}(s, C_v(\phi _{\tau }))$.

If there is no vertex on $P_{\tau }$ that satisfies both (N1) and (N2), then let $\phi _{\tau }$ be the first vertex incident to the first missing edge on $P_{\tau } {\setminus } E(G_\tau )$ (i.e., such that $P_{\tau }[s,\phi _{\tau }]$ is the maximal prefix that is contained in $G_{\tau }$).

Let $Q_{\tau }=P_{\tau }[\phi _{\tau },t]$ and define $\mathtt{Cost}(P_\tau )=|E(Q_{\tau }) {\setminus } E(G_\tau )|$ be the number of edges of $Q_{\tau }$ that are missing in the current subgraph $G_\tau$. Thus $\mathtt{Cost}(P_\tau )$ represents the increase in the size of the spanner $G_\tau$ if the procedure adds $Q_\tau$. Our algorithm attempts to buy only the suffix $Q_\tau$ of $P_{\tau }$ when considering $P_{\tau }$. We now define the set $\mathtt{ValSet}(P_{\tau }) \subseteq {\mathcal {C}} \times {\mathcal {C}}$ which contains a collection of ordered cluster pairs. Let $C_{1,\tau }=C_v(\phi _{\tau })$ and $C_{2,\tau }=C_v(t)$ be the clusters of $\phi _{\tau }$ and t in $G_{\varDelta } {\setminus } \{v\}$. Let $\kappa =\mathtt{Cost}(P_{\tau })$. The candidate $P_{\tau }$ is said to be cheap if $\kappa \le 4$, otherwise it is costly. The definition of $\mathtt{ValSet}(P_{\tau })$ depends on whether or not the path is cheap. In particular, if $P_{\tau }$ is cheap, then let $\mathtt{ValSet}(P_{\tau })=\{(C_{1,\tau }, C_{2,\tau })\}$ only if

$$\begin{aligned} \mathrm{dist}(\phi _{\tau }, t, P_\tau )< \mathrm{dist}(C_{1,\tau }, C_{2,\tau }, G_\tau {\setminus } V_{f}(C_{2,\tau })), \end{aligned}$$

(27)

where $V_{f}(C_{2,\tau })$ is as given by Eq. (3), and let $\mathtt{ValSet}(P_{\tau })=\emptyset$ otherwise. Alternatively, if $P_{\tau }$ is costly, we do the following.

Definition 4

Let $U_{s,t,v}=\{u_{3\ell +1} ~\mid ~ \ell \in \{0, \ldots , \lfloor (\kappa -1)/3 \rfloor \}\} \subseteq Q_{\tau }$ be some representative endpoints of missing edges on $Q_{\tau }$ satisfying that

$$\begin{aligned}&\mathtt{LastE}(Q_{\tau }[\phi _{\tau }, u_{\ell }]) \notin G_{\tau } \text{ for } \text{ every } u_{\ell } \in U_{s,t,v}\\&\quad \text{ and } \mathrm{dist}(u_{\ell }, u_{\ell '}, Q_{\tau })\ge 3~ \end{aligned}$$

for every $u_\ell , u_{\ell '} \in U_{s,t,v}$.

Define

$$\begin{aligned}&\mathtt{ValSet}_1(P_{\tau })~=~\{(C_{1,\tau }, C_\ell ) ~\mid ~ C_\ell =C_{v}(u_\ell ), u_{\ell } \in U_{s,t,v}\nonumber \\&\quad \text{ and }~ \mathrm{dist}(\phi _\tau , u_\ell , P_{\tau }) < \mathrm{dist}(C_{1,\tau }, C_\ell , G_{\tau } {\setminus } V_{f}(C_\ell ))\}\nonumber \\ \end{aligned}$$

(28)

and

$$\begin{aligned}&\mathtt{ValSet}_2(P_{\tau })~=~\{(C_\ell ,C_{2,\tau }) ~\mid ~ C_\ell =C_{v}(u_\ell ), u_{\ell } \in U_{s,t,v} \nonumber \\&\quad \text{ and }~ \mathrm{dist}(u_\ell , t, P_{\tau }) < \mathrm{dist}(C_\ell , C_{2,\tau }, G_{\tau } {\setminus } V_{f}(C_{2,\tau }))\}\nonumber \\ \end{aligned}$$

(29)

Let $\mathtt{ValSet}(P_{\tau })=\mathtt{ValSet}_1(P_{\tau })\cup \mathtt{ValSet}_2(P_{\tau })$. The subpath $Q_\tau$ is added to $G_{\tau }$ resulting in $G_{\tau +1}$ only if

$$\begin{aligned} \mathtt{Cost}(P_\tau ) \le 4 \cdot \mathtt{Val}(P_\tau ), \end{aligned}$$

(30)

where $\mathtt{Val}(P_\tau )=|\mathtt{ValSet}(P_{\tau })|$. (Note that when $P_{\tau }$ is cheap, Eq. (30) holds iff Eq. (27) holds.) The output of Alg. Cons8SWSpanner is the subgraph $H_8(S)=G_{\tau '}$ where $\tau '=|{\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}|.$ This completes the description of the algorithm.

Analysis Throughout the discussion, a path $P_{s,t,v}$ is a new-ending path, if $\mathtt{LastE}(P_{s,t,v})\notin G_0$ (see Eq. (2)). Hence, we consider only $P_{s,t,v} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$ paths for clustered vertices $t \in V_{C}$.

For a new-ending path $P_{s,t,v}$, recall that $b_{s,t,v}$ is the unique divergence point of $P_{s,t,v}$ and $\pi (s,t)$ and let $D_{s,t,v}$ be the detour segment, i.e., $D_{s,t,v}=P_{s,t,v}[b_{s,t,v},t]$ and $D^-_{s,t,v}=D_{s,t,v}{\setminus } \{b_{s,t,v}\}$. Let $Q_{s,t,v}=P_{s,t,v}[\phi _{s,t,v}, t]$ be the path segment that was considered to be bought in step (4.2) (see Definition 3).

Observation 11

$Q_{s,t,v} \subseteq D^-_{s,t,v}$.

Proof

Let x be the first vertex incident to a missing-edge on $P_{s,t,v}$ (such that $P_{s,t,v}[s,x]$ is the maximal prefix that is contained in $G_0$). Since $\phi _{s,t,v}$ occurs not before x on $P_{s,t,v}$ the observation follows by Lemma 4(b). $\square$

The main essence of the path-buying procedure (in the fault-free setting) is that the number of distance improvements between any fixed pair of clusters with bounded diameter is bounded. This essential argument fails to hold when the distances are measured in different subgraphs. Since in the FT setting the candidate path to be bought, $P_{s,t,v}$, should be compared against some alternative path in the current spanner $H' {\setminus } \{v\}$, the distances between clusters might be evaluated in distinct subgraphs. Hence, the main challenge in adapting the path-buying scheme to the FT setting is in showing that due to the special structure of the independent paths $P_{s,t,v}$, the distance improvements between any pair of clusters $C_1$ and $C_2$ that are incident on $P_{s,t,v}$ can be carried out in the “same” subgraph, i.e., a subgraph that depends only on the clusters $C_1$ and $C_2$ and independent of the source s and the failing vertex v. The independence of the source s is given by the fact that the paths are independent and hence their internal detour segments does not intersects any $\pi (s',t)$ path, for $s' \in S$. The independence of the failing vertex v is due to the fact that all failing events occur above the least common ancestor of the cluster members in the BFS tree rooted at s. The next lemma formalizes some of the above intuition and provide the key properties that enables the definition of the graph in which the path $P_{s,t,v}$ would be evaluated in our path-buying scheme.

Lemma 12

Let $P_{s,t,v} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$ be a new-ending replacement path. Then for every $u_k \in U_{s,t,v} \cup \{t\}$ with $C_k=C_v(u_k)$ it holds that:

• (a) $C_k=C_1(u_k)$.

• (b) $V(P_{s,t,v}[b_{s,t,v}, u_k]) \cap V(T(u_k,S))=\{b_{s,t,v},u_k\}$.

• (c) $Q_{s,t,v}[\phi _{s,t,v},u_k]\cap V_{f}(C_k)=\emptyset$.

• (d) $v \in V_{f}(C_k)$.

Proof

We begin with (a). By the uniqueness of the weight assignment W, $P_{s,t,v}[s,u_k]=P_{s,u_k,v}=SP(s, u_k, G {\setminus } \{v\},W)$. By the uniqueness of the divergence point $b_{s,t,v}$ and in particular by Lemma 2(b),

$$\begin{aligned} b_{s,t,v}=b_{s,u_k,v}. \end{aligned}$$

(31)

Since $\mathtt{LastE}(P_{s,u_k,v}) \notin E^{\mathtt{local}}$, it follows that $u_k \in V_{C}$, $v \ne z_1(u_k)$. Hence $z_v(u_k)=z_1(u_k)$ and (a) holds.

Consider (b). By the definition of the set $U_{s,t,v}$ (see Definition 4), it holds $\mathtt{LastE}(P_{s,u_k,v}) \notin G_0$. Since $u_k \in Q_{s,t,v}$ occurs strictly after $\phi _{s,t,v}$, by the Definition 3, it holds that $u_k$ did not satisfy property (N2). Hence, since $\mathtt{LastE}(P_{s,u_k,v}) \notin E^{\mathtt{local}}$, $v \notin \{z_1(u_k), \mathtt{LCA}(s, C_k)\}$ and hence $v \in V^{\mathtt{far}}(s,u_k)$. As $\mathtt{LastE}(P_{s,u_k,v}) \notin E^{\mathtt{far}}_{\mathtt{dep}}(u_k)$, we get that $P_{s,u_k,v}$ is a new-ending independent path. By Eq. (1), $V(P_{s,u_k,v}[b_{s,u_k,v}, u_k]) \cap V(T(u_k,S))=\{b_{s,u_k,v}, u_k\}$. Hence (b) holds by Eq. (31).

We now turn to consider claim (c). By Eq. (3), $V_{f}(C_k) \subseteq T(u_k,S)$. Since $C_v(u_k) \cap V_{f}(C_k)=\emptyset$, it holds that $u_k \notin V_{f}(C_k)$, and hence by combining with claim (b), we get that $P_{s,u_k,v}[b_{s,u_k,v},u_k]\cap V_{f}(C_k)=\{b_{s,u_k,v}\}$. Since by Observation 11, $\phi _{s,t,v} \ne b_{s,u_k,v}$, hence $Q_{s,t,v}[\phi _{s,t,v},u_k]\cap V_{f}(C_k)=\emptyset$. Claim (c) holds.

Consider claim (d). By the above, v occurs on the far segment $\pi (s, C_k) {\setminus } \{\mathtt{LCA}(s,C_k)\}$, hence $v \notin C_k$. Since $(\pi (s, C_k) {\setminus } C_k) \subseteq V_{f}(C_k)$, (d) holds. $\square$

The next observation is useful in our analysis.

Observation 12

If $\phi _{s,t,v}$ satisfies (N1) and (N2), then there exists a vertex $x \in C_{v}(\phi _{s,t,v})$ satisfying that $v \notin V(\pi (s,x))$.

Proof

Let $P_{\tau }=P_{s, t, v}$ and $\phi _\tau =\phi _{s,t,v}$. By the uniqueness of the weight assignment W, $P_{\tau }[s, \phi _{\tau }]=P_{s, \phi _{\tau },v}=SP(s, \phi _\tau , G {\setminus } \{v\},W)$. Since $\phi _{\tau }$ satisfies (N2), it holds that the failing vertex v occurs on $\pi ^{\mathtt{near}}(s, \phi _\tau )$, strictly below (i.e., closer to $\phi _\tau )$ the least common ancestor $\mathtt{LCA}(s, C_v(\phi _{\tau }))$ on $\pi (s,\phi _\tau )$. Hence, there must exist a vertex $x \in C_v(\phi _{\tau })$ such that $v \notin V(\pi (s,x))$ (otherwise, if v is shared by $\pi (s,u)$ for all cluster members u, then we end with contradiction to the definition of the least common ancestor $\mathtt{LCA}(s, C_v(\phi _{\tau }))$). $\square$

We proceed by showing correctness.

Theorem 13

$H_8(S)$ is a (8, S) FT-spanner.

Proof

Let $H=H_8(S)$. It is required to show that $\mathrm{dist}(s, t, H {\setminus } \{v\}) \le \mathrm{dist}(s, t, G {\setminus } \{v\})+8$ for every $(s,t) \in S \times V$ and $v \in V$. By the analysis of Alg. Cons4SWSpanner (Lemma 5), it remains to consider the case of independent new-ending paths where $P_{s,t,v} \in {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}(t)$ for $t \in V_{C}$.

Let $\tau$ be the iteration at which $P_{\tau }=P_{s,t,v}$ was considered to be added to the spanner at step (4.2), and let $\kappa =\mathtt{Cost}(P_{\tau })$ denote its cost. Let $\phi _{\tau }$ be as defined in Definition 3 and recall that $Q_{\tau }=P_{\tau }[\phi _{\tau },t]$ is the candidate suffix to be bought by the procedure. (In particular, $\mathtt{Cost}(P_{\tau })$ counts the number of edges on $Q_\tau {\setminus } E(G_{\tau })$.)

Case (1): $Q_{\tau }$ was bought If $\phi _{\tau }$ did not satisfy either properties (N1) or (N2), then $P_{\tau }[s, \phi _\tau ] \subseteq G_{\tau }$. Since $P_{\tau }=P_{\tau }[s, \phi _{\tau }]\circ Q_{\tau }$ and $Q_{\tau }$ was added to the spanner, we get that $P_{\tau } \subseteq H {\setminus } \{v\}$.

It remains to consider the complementary case where $\phi _{\tau }$ satisfies both (N1) and (N2). By Observation 12, we get that there exist $x \in C_{v}(\phi _{\tau })$ satisfying that $v \notin V(\pi (s,x))$.

Consider the path $P=\pi (s,x) \circ (x, z_v(\phi _{\tau }),\phi _{\tau })$. By definition, $P \subseteq H {\setminus } \{v\}$ and by the existence of the intracluster path connecting x and $\phi _\tau$ in $G {\setminus } \{v\}$, it holds that $|P|=\mathrm{dist}(s,x, G {\setminus } \{v\})+2 \le \mathrm{dist}(s,\phi _\tau , G {\setminus } \{v\})+4$. Hence, letting $P'=P \circ Q_{\tau }$ (where $Q_\tau =P_{\tau }[\phi _\tau ,t]$), since $Q_\tau \subseteq H {\setminus } \{v\}$, it holds that $P' \subseteq H {\setminus } \{v\}$ and $|P'|\le |P_{\tau }|+4$, as required.

Case (2): $Q_{\tau }$ was not bought Let $x \in C_v(\phi _{\tau })$ be defined as follows. If $\phi _{\tau }$ satisfies both properties (N1) and (N2) of Definition 3, then using Observation 12, let $x \in C_{v}(\phi _{\tau })$ be the vertex satisfying that $v \notin V(\pi (s,x))$. Otherwise, if $\phi _{\tau }$ did not satisfy (N1) or (N2) (or both), let $x=\phi _{\tau }$. Note that in any case, it holds that $x, \phi _\tau \in C_v(\phi _\tau )$. We have the following.

Lemma 13

$P_{s,x,v} \subseteq H {\setminus } \{v\}$.

Proof

If $x=\phi _{\tau }$, then it implies that $\phi _\tau$ did not satisfy both of the properties (N1,N2). By Definition 3, in such a case $\phi _\tau$ is the vertex incident to the first missing edge on $P_{s,t,v} {\setminus } E(G_\tau )$ and hence $P_{s,t,v}[s,x]=P_{s,x,v} \subseteq G_{\tau } {\setminus } \{v\}$.

Otherwise, if $x \ne \phi _{\tau }$, then $x \in C_v(\phi _\tau )$ and by the selection of x, $v \notin V(\pi (s,x))$. Hence, $P_{s,x,v}=\pi (s,x) \subseteq H {\setminus } \{v\}$. $\square$

Recall that $C_{1,\tau }=C_v(\phi _\tau )$ and $C_{2,\tau }=C_v(t)$. In addition, since $v \in V^{\mathtt{far}}(s,t)$, it holds that $v \in V_f(C_{2,\tau })$.

Case (2.1): $P_{\tau }$ is cheap Since $Q_{\tau }$ was not added, Eq. (27) did not hold and hence

$$\begin{aligned} \mathrm{dist}(\phi _{\tau },t,P_{\tau })\ge \mathrm{dist}(C_{1,\tau },C_{2,\tau },G_{\tau } {\setminus } V_f(C_{2,\tau })). \end{aligned}$$

(32)

Let $w_1 \in C_{1,\tau }$ and $w_2 \in C_{2,\tau }$ be a closest pair satisfying that $\mathrm{dist}(w_1, w_2, G_{\tau } {\setminus } V_{f}(C_{2,\tau }))=\mathrm{dist}(C_{1,\tau }, C_{2,\tau }, G_{\tau } {\setminus } V_{f}(C_{2,\tau }))$. Since the failing vertex v is in $V_f(C_{2,\tau })$, both auxiliary vertices $w_1$ and $w_2$ are in $G {\setminus } \{v\}$. Consider the following $s-t$ path: $P=P_0 \circ P_1 \circ P_2 \circ P_3$ where $P_0=P_{s,x,v}$, $P_1=[x, z_v(\phi _\tau ), w_1]$, $P_2 \in SP(w_1, w_2, G_{\tau } {\setminus } V_{f}(C_{2,\tau }))$, and $P_3=[w_2, z_v(t), t]$. For an illustration see Fig. 4. By Lemma 13, $P_0 \subseteq H {\setminus } \{v\}$. Note that since $x, w_1 \in C_v(\phi _\tau )$, the path $P_1$ exists in $H {\setminus } \{v\}$. Combining with the definitions of the vertices $z_v(x), z_v(t),w_1,w_2$, it holds that $P \subseteq H {\setminus } \{v\}$. So, it remains to bound the length of the path.

$$\begin{aligned}&\mathrm{dist}(s, t, H {\setminus } \{v\}) \le |P_0|+|P_1|+|P_2|+|P_3| \nonumber \\&\quad = \mathrm{dist}(s,x,G {\setminus } \{v\})\!+\!\mathrm{dist}(w_1, w_2, G_{\tau } {\setminus } V_{f}(C_{2,\tau }))\!+\!4 \nonumber \\&\quad \le \mathrm{dist}(s,\phi _\tau ,G {\setminus } \{v\}) \nonumber \\&\quad \quad +\, \mathrm{dist}(w_1, w_2, G_{\tau } {\setminus } V_{f}(C_{2,\tau }))+6 \end{aligned}$$

(33)

$$\begin{aligned}&\quad \le \mathrm{dist}(s,\phi _\tau ,G {\setminus } \{v\})+\mathrm{dist}(\phi _\tau , t, P_{\tau })+6~=|P_{\tau }|+6, \nonumber \\ \end{aligned}$$

(34)

where Eq. (33) follows by the fact that $x,\phi _{\tau } \in C_v(\phi _{\tau })$ and since $G_{\varDelta } \subseteq H$, it holds that the intracluster path $R=[x, z_v(\phi _\tau ), \phi _\tau ]$ exists in $G {\setminus } \{v\}$, Eq. (34) follows by Eq. (32).

Case (2.2): $P_{\tau }$ is costly Let $U_{s,t,v}=\{u_{1}, \ldots , u_{\kappa '}\} \subseteq Q_{\tau }$ for $\kappa '=\lfloor \kappa /3 \rfloor \ge 1$ be as defined by Definition 4. Since by Observation 5, the diameter of each cluster is 2, each $u_{k}\in U_{s,t,v}$ belongs to a distinct cluster $C_{k}=C_v(u_{k}) \in {\mathcal {C}}$. Hence there are at least $\kappa '$ distinct clusters on $Q_{\tau }$.

A cluster $C_{k}=C_v(u_{k})$ is a contributor if adding $Q_\tau$ to $G_\tau$ improves either the $C_{1,\tau }-C_{k}$ distance (i.e., $(C_{1,\tau },C_k) \in \mathtt{ValSet}_1(P_{\tau })$) or the $C_{2,\tau }-C_{k}$ distance (i.e., $(C_k,C_{2,\tau }) \in \mathtt{ValSet}_2(P_{\tau })$) in the corresponding appropriate graph. Otherwise, $C_{k}$ is neutral. There are two cases to consider. If all clusters are contributors (i.e., there is no neutral cluster) then all the $\kappa '$ clusters contribute to $\mathtt{Val}(P_\tau )$ (either with $C_{1,\tau }$ or with $C_{2,\tau }$ or both). It then holds that $\mathtt{Val}(P_{\tau })\ge \kappa ' \ge \mathtt{Cost}(P_\tau )/4$. Hence, by Eq. (30), we get a contradiction to the fact that the suffix $Q_\tau$ was not added to $G_\tau$.

Fig. 4

Schematic illustration of the path-buying procedure of Alg. Cons8SWSpanner. The horizontal path is $P_{\tau }=P_{s,t,v}$ whose segment $Q_{s,t,v}=P_{s,t,v}[\phi _{s,t,v},t]$ was considered to be bought at time $\tau$. The green paths correspond to the shortest paths in $T_0(s)$. Red edges correspond to missing edges on $P_{s,t,v} {\setminus } E(G_{\tau })$. The vertex $\phi _{s,t,v}$ satisfies properties (N1) and (N2), hence it is incident to a missing edge and the failing vertex v occurs on $\pi (s, \phi _{s,t,v})$ strictly below the LCA vertex $\mathtt{LCA}(\phi _{s,t,v})=\mathtt{LCA}(s, C_v(\phi _{s,t,v}))$. The vertex $x \in C_v(\phi _{s,t,v})$ satisfies that $v \notin V(\pi (s,x))$. The $s-t$ replacement path in $H {\setminus } \{v\}$ is given by traveling from s to x on $\pi (s,x)$ and then use the closest vertex pairs $w_1,w_2$ and $y_1,y_2$ (color figure online)

In the other case, there exists at least one neutral cluster $C_{\ell }$ such that

$$\begin{aligned} \mathrm{dist}(C_{1,\tau }, C_{k} , \widehat{H}_{1})\le & {} \mathrm{dist}(\phi _\tau , u_{k} ,P_{\tau }) \text{ and } \\ \mathrm{dist}(C_{k} , C_{2,\tau }, \widehat{H}_{2})\le & {} \mathrm{dist}(u_{k},t ,P_{\tau }),\nonumber \end{aligned}$$

(35)

where $\widehat{H}_{1}=G_{\tau } {\setminus } V_{f}(C_{k})$ and $\widehat{H}_{2}=G_{\tau } {\setminus } V_{f}(C_{2,\tau })$. Let $w_1 \in C_{1,\tau }$ and $w_2 \in C_{k}$ be the pair of vertices satisfying $\mathrm{dist}(w_1,w_2 , \widehat{H}_{1})=\mathrm{dist}(C_{1,\tau }, C_{k} , \widehat{H}_{1})$. In addition, let $y_1 \in C_k$ and $y_2 \in C_{2,\tau }$ be the pair satisfying $\mathrm{dist}(y_1,y_2 , \widehat{H}_{2})=\mathrm{dist}(C_{k} , C_{2,\tau }, \widehat{H}_{2})$.

Let $Q_1=[x, z_v(\phi _\tau ), w_1]$, $Q_2=[w_2, z_v(u_{k}), y_1]$ and $Q_3=[y_2, z_v(t), t]$ be the intracluster paths in $C_{1,\tau },C_k$ and $C_{2,\tau }$ respectively. Note that by definition $x,w_1 \in C_v(\phi _\tau )$.

Since by Lemma 12(d), $v \in V_{f}(C_k) \cap V_{f}(C_{2,\tau })$, it also holds that $Q_1, Q_2, Q_3 \subseteq H {\setminus } \{v\}$. Let $P'=P_0 \circ Q_1 \circ P_1 \circ Q_2 \circ P_2 \circ Q_3$ where $P_0=P_{s,x,v}$, $P_1 \in SP(w_1, w_2, \widehat{H}_{1})$ and $P_2 \in SP(y_1, y_2, \widehat{H}_{2})$. By Lemma 13, $P_0 \subseteq H {\setminus } \{v\}$ and by the above explanation, $P' \subseteq H {\setminus } \{v\}$. So, it remains to bound the length of the $s-t$ path $P'$.

$$\begin{aligned}&\mathrm{dist}(s, t, H {\setminus } \{v\}) \le |P'|=|P_0|+|P_1|+|P_2|+6\\&\quad = \mathrm{dist}(s,x, G{\setminus } \{v\})+\mathrm{dist}(w_1, w_2, \widehat{H}_{1})\\&\quad +\, \mathrm{dist}(y_1,y_2, \widehat{H}_{2})+6\\&\quad \le \mathrm{dist}(s,\phi _\tau , G{\setminus } \{v\})+\mathrm{dist}(w_1, w_2, \widehat{H}_{1})\\&\quad +\, \mathrm{dist}(y_1,y_2, \widehat{H}_{2})+8\\&\quad = \mathrm{dist}(s,\phi _\tau , G{\setminus } \{v\})+\mathrm{dist}(C_{1,\tau }, C_{k}, \widehat{H}_{1})\\&\quad \quad + \, \mathrm{dist}(C_{k}, C_{2,\tau }, \widehat{H}_{2})+8\\&\quad \le \mathrm{dist}(s,\phi _\tau , G{\setminus } \{v\})+\mathrm{dist}(\phi _\tau , u_{k}, P_{\tau })\\&\quad +\,\mathrm{dist}(u_{k}, t, P_{\tau })+8\\&\quad = |P_{s,t,v}|+8, \end{aligned}$$

where the first inequality follows by the fact that $x,\phi _\tau \in C_v(\phi _\tau )$ and hence the intracluster path $R=[x, z_v[\phi _\tau ], \phi _\tau ]$ exists in $G {\setminus } \{v\}$ and last inequality follows Eq. (35). The lemma follows. $\square$

Finally, we turn to bound the size of $H=H_8(S)$. By the size-analysis of Alg. Cons4SWSpanner, it remains to bound the number of edges added due to the path-buying procedure of step (4.2). Let ${\mathcal {B}} \subseteq {\mathcal {P}}^{\mathtt{far}}_{\mathtt{indep}}$ be the set of paths corresponding to the path segments that were bought in the path-buying phase. For every ordered pair of clusters, $C_1, C_2 \in {\mathcal {C}}$ let ${\mathcal {B}}(C_1, C_2)=\{ P_{\tau } \in {\mathcal {B}} ~\mid ~ (C_1, C_2) \in \mathtt{ValSet}(P_{\tau })\}$. Clearly, ${\mathcal {B}}=\bigcup _{C_1, C_2 \in {\mathcal {C}}} {\mathcal {B}}(C_1, C_2)$. We next claim that since the diameter of each cluster is small, it holds that the cardinality of each subset ${\mathcal {B}}(C_1, C_2)$ is small as well.

Lemma 14

$|{\mathcal {B}}(C_1, C_2)| \le 5$ for every $C_1, C_2 \in {\mathcal {C}}$.

Proof

Fix $C_1, C_2 \in {\mathcal {C}}$ and let ${\mathcal {B}}(C_1, C_2)=\{P_{\tau _1}, \ldots , P_{\tau _N}\}$ be sorted according to the time $\tau _k$ their segment $Q_{\tau }$ was added to the spanner, for every $k \in \{1, \ldots , N\}$ where $N=|{\mathcal {B}}(C_1, C_2)|$. Let $P_{\tau _k}=P_{s_k,t_k,v_k}$. Let $p_k, q_k \in U_{s_k,t_k,v_k}$ be the endpoints of $Q_{\tau }$ such that $p_k$ is closer to the source $s_k$, and $C_{v_k}(p_k)=C_1$ and $C_{v_k}(q_k)=C_2$.

Recall that $\phi _{\tau _k}$ is the first vertex of $Q_{\tau _k}$ (see Definition 3). Let $C_\ell =C_{v_k}(u_\ell )$ be the cluster of $u_{\ell }$ for every $u_\ell \in U_{s_k,t_k,v_k}$ (see Definition 4). By Observation 5, it holds that $C_{\ell } \ne C_{\ell '}$ for every $u_{\ell },u_{\ell '} \in U_{s_k,t_k,v_k}$. Recall that for every $u_\ell \in U_{s_k,t_k,v_k}$, $P_{s,u_{\ell },v}=P_{s,t,v}[s,u_{\ell }]$. Since $\mathtt{LastE}(P_{s,u_\ell ,v}) \notin E^{\mathtt{local}}$, it holds that $v \notin \{z_1(u_{\ell }), \mathtt{LCA}(s, C_1(u_{\ell }))\}$. Combining that with the fact that $u_\ell \in U_{s_k,t_k,v_k}$ did not satisfy property (N2) (see Definitions 3 and 4), we conclude that $v_k \in V^{\mathtt{far}}(s_k, u_\ell )$. Since $q_k \in U_{s_k,t_k,v_k} \cup \{t_k\}$, using Lemma 12(d), it holds that

$$\begin{aligned} v_k \in V_{f}(C_2) \text{ for } \text{ every } k \in \{1,\ldots ,N\}, \end{aligned}$$

(36)

and by Lemma 12(c),

$$\begin{aligned} P_{\tau _k}[p_k, q_k] \subseteq Q_{\tau _k}[p_k, q_k] \subseteq G {\setminus } V_{f}(C_2). \end{aligned}$$

(37)

Since $C_1=C_{v_k}(p_k)$ and $C_2=C_{v_k}(q_k)$, for every $k \in \{1, \ldots , N\}$, it holds that $z_{v_{1}}(p_1)=\cdots =z_{v_{N}}(p_N)$ and also $z_{v_{1}}(q_1)=\cdots =z_{v_{N}}(q_N)$. Hence, letting $z_1=z_{v_{1}}(p_1)$ and $z_2=z_{v_{1}}(q_1)$, it holds that

$$\begin{aligned} z_1,z_2 \notin \{v_1, \ldots , v_N\}. \end{aligned}$$

(38)

Denote

$$\begin{aligned} X_k=\mathrm{dist}(p_k, q_k, G_{\tau _{k+1}} {\setminus } V_{f}(C_2)). \end{aligned}$$

We now show that $X_k<X_{k-1}$ for every $k \in \{2, \ldots N\}$.

Each time a path segment $Q_{\tau _k}$ is purchased at time $\tau _k$, it implies that

$$\begin{aligned} X_k\le & {} \mathrm{dist}(p_k, q_k, P_{\tau _k} {\setminus } V_{f}(C_2)) \end{aligned}$$

(39)

$$\begin{aligned}= & {} \mathrm{dist}(p_k, q_k,P_{\tau _k}) \end{aligned}$$

(40)

$$\begin{aligned}< & {} \mathrm{dist}(C_{1}, C_{2}, G_{\tau _{k}} {\setminus } V_{f}(C_2)) \end{aligned}$$

(41)

$$\begin{aligned}\le & {} X_{k-1}, \end{aligned}$$

(42)

where Eq. (39) follows by the fact that $P_{\tau _k}[p_k, q_k] \subseteq Q_{\tau _k} \subseteq G_{\tau _{k+1}}$, Eq. (40) follows by Eq. (37), Eq. (41) follows by the fact that $Q_{\tau _k}$ was bought and by Eqs. (28) and (29), and Eq. (42) follows by the fact that $p_{k-1} \in C_1$ and $q_{k-1} \in C_2$.

Therefore, we have that

$$\begin{aligned} X_N \le X_1-(N-1). \end{aligned}$$

(43)

Conversely, we have that

$$\begin{aligned} X_N\ge & {} \mathrm{dist}(p_{N}, q_N, G {\setminus } \{v_1, \ldots , v_N\}) \end{aligned}$$

(44)

$$\begin{aligned}\ge & {} \mathrm{dist}(p_1, q_1, G {\setminus } \{v_1, \ldots , v_N\})-4 \end{aligned}$$

(45)

$$\begin{aligned}= & {} \mathrm{dist}(p_1, q_1, P_{\tau _1})-4 \nonumber \\= & {} \mathrm{dist}(p_1, q_1, P_{\tau _1} {\setminus } V_{f}(C_2))-4 \end{aligned}$$

(46)

$$\begin{aligned}\ge & {} X_1-4, \end{aligned}$$

(47)

where Eq. (44) follows as $G_{\tau _{N+1}} \subseteq G$ and by Eq. (36), $\{v_1, \ldots , v_N\} \subseteq V_{f}(C_2)$. To see Eq. (45), note that $p_{1},p_N \in C_{1}$ and $q_1,q_N \in C_{2}$ and by Observation 5(2) the diameter of the cluster is 2. It remains to show that the intracluster paths $R_1=[p_1, z_1, p_N], R_2=[q_1, z_2, q_N]$ exist in the surviving graph $G {\setminus } \{v_1, \ldots , v_N\}$. This holds since by Eq. (38), $z_1,z_2 \notin \{v_1, \ldots , v_N\}$, and by Eqs. (36) and (37). Equation (46) follows by Eq. (37). Finally, Eq. (47) follows by the fact that $P_{\tau _1}[p_1,q_1]\subseteq Q_{\tau _1}$ was added at step $\tau _1$, hence $P_{\tau _1}[p_1,q_1] \subseteq G_{\tau _{2}}$. By combining with Eq. (43), we get that $N \le 5$. The lemma follows. $\square$

We now claim the following.

Lemma 15

$|E(H_8(S))|=O(|S| \cdot n+ n^{2}/|S|^2)$.

Proof

Since for every path $P \in {\mathcal {B}}$, it holds that $\mathtt{Cost}(P) \le 4 \cdot \mathtt{Val}(P)$, we get that

$$\begin{aligned} |E(G_{\tau '}) {\setminus } E(G_0)|= & {} \sum _{P \in {\mathcal {B}}} \mathtt{Cost}(P) \le 4 \sum _{P \in {\mathcal {B}}} \mathtt{Val}(P)\\\le & {} 4 \sum _{C_1, C_2 \in {\mathcal {C}}} |{\mathcal {B}}(C_1, C_2)|\\\le & {} O(|{\mathcal {C}}|^2)=O((n/|S|)^2). \end{aligned}$$

where the last equality follows by the fact that there are $|{\mathcal {C}}|=|Z|=O(n/|S|)$ clusters. The claim follows. $\square$

Additive stretch 6 (for all pairs) Set $\varDelta =\sqrt{n}$ and let $Z \subseteq S$ be a collection of $\sqrt{n}$ cluster centers and $G_{\varDelta }$ be the corresponding clustering graph. By Observation 1, $H=H_4(Z) \cup G_{\varDelta }$ is a 6 additive FT-spanner. By Theorem 8, $|E(H_4(Z))|=O(n^{3/2})$ and by Observation 5(4), $|E(G_{\varDelta })|=O(n^{3/2})$, hence Theorem 3 follows.

The achieved bounds should be compared with the single source additive FT-spanner $H_4(\{s\})$ of [21] and the (all-pairs, non FT) 6-additive spanner, both with $O(n^{4/3})$ edges.

5 Discussion

The current work provides the first upper bounds for handling vertex faults in additive spanner constructions. Unfortunately, currently there is no lower bound for this setting. Specifically, even for the basic case of additive stretch 2, there is no lower bound of $\Omega (n^{3/2+\epsilon })$ for any $\epsilon >0$. In [21], there is a lower bound construction for the single source FT-additive spanners. Extending this lower bound for (all pairs) FT-additive spanners remains open. Turning to the upper bound side, there are two main challenges. The first involves the construction of FT structures with nonconstant additive stretch (e.g., polylogarithmic or sublinear in the distances). The second involves the extension of the presented constructions to support the case of multiple vertex faults.