## Vertex Fault Tolerant Additive Spanners

Merav Parter ∗

August 5, 2014

## 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 dist( s, t, H \ { v } ) ≤ dist( s, t, G \ { v } ) + β for every s, t, v ∈ V . Recently, the problem of constructing fault-tolerant additive spanners resilient to the failure of up to f edges has been considered [8]. 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 adopted 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 × V for a given subset of sources S ⊆ V . The additive stretch bounds of our constructions are 4 and 8 (using a different number of edges).

## 1 Introduction

An ( α, β )-spanner H of an unweighted undirected graph G is a spanning subgraph satisfying for every pair of vertices s, t ∈ V that dist( s, t, H ) ≤ α · dist( s, t, G ) + β . When β = 0, the spanner is termed a multiplicative spanner and when α = 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 β = 2 4 6 , , with O n ( 3 2 / ) , O ˜ ( n 7 5 / ) and O n ( 4 3 / ) edges respectively [1, 2, 5, 11, 14, 15]. This paper considers a network G that may suffer single vertex failure events, and looks for fault tolerant additive spanners that maintain their additive stretch guarantee under failures. Formally, a subgraph H ⊆ G is a β -additive FT-spanner iff for every ( s, t ) ∈ V × V and for every failing vertex v ∈ V , dist( s, t, H \ { v } ) ≤ dist( s, t, G \ { v } ) + β . 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

∗ Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel. E-mail: { merav.parter @ } weizmann.ac.il . Recipient of the Google European Fellowship in distributed computing; research is supported in part by this Fellowship. Supported in part by the Israel Science Foundation (grant 894/09).

simply lease a 2-additive spanner H 0 of the graph with Θ( n 3 2 / ) edges. However, if one of the vertices in the graph fails, some s -t routes in H 0 \ { v } might be significantly longer than the corresponding route in the surviving graph G \ { v } . Moreover, s and t are not even guaranteed to be connected in H 0 \ { 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 at el. [10] for the case of multiplicative stretch. Specifically, [10] presented algorithms for constructing an f -vertex fault tolerant spanner with multiplicative stretch (2 k -1) and O f k ( 2 f +1 · n 1+1 /k log 1 -1 /k n ) edges. Dinitz and Krauthgamer presented in [13], a randomized construction attaining an improved tradeoff for vertex fault-tolerant spanners, namely, f -vertex fault tolerant k -spanner with ˜ O f ( 2 · n 1+2 ( / k +1) ) edges. Constructions of fault-tolerant spanners with additive stretch resilient to edge failures were recently given by Braunschvig at el. [8]. They establish the following general result. For a given n -vertex graph G , let H 1 be an ordinary additive (1 , β ) spanner for G and H 2 be a ( α, 0) fault tolerant spanner for G resilient against up to f edge faults. Then H = H 1 ∪ H 2 is a (1 , β ( f )) additive fault tolerant spanner for G (for up to f edge faults) for β f ( ) = O f α ( ( + β )). In particular, fixing the number of H edges to be O n ( 3 2 / ) and the number of faults to f = 1 yields an additive stretch of 14. Hence, in particular, there is no construction for additive stretch &lt; 14 and o n ( 2 ) edges. In addition, note that these structures are resilient only to edge failures as the techniques of [8] 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 [8].

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 ∈ 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, 16, 19, 21]) 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 ⊆ V have been studied in [17], which defines the notion of an FT-MBFS structure H ⊆ G containing the collection of all replacement paths P s,t,v for every pair ( s, t ) ∈ S × V for a given subset of sources S and a failing vertex v ∈ V . Hence, FT-MBFS structures preserve the exact s -t distances in G \ { v } for every failing vertex v , for every source s ∈ S .

It is shown in [17] 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 ( √ | S | · 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 ⊆ V , for which every FT-MBFS structure is of size Ω( √ | S | · 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 ˜ P s,t,v (i.e., such that | ˜ P s,t,v | ≤ α · | P s,t,v | ) has been studied in [3, 9, 6]. In particular its single source variant has been studied in [4, 18]. 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 β for every source s ∈ 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 (max { n · | S , | ( n/ S | | ) 3 } ) edges and the second construction guarantees additive stretch 8 with ˜ O (max { n · | 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.

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, where the objective is to construct a subgraph H ⊆ G that satisfies the bounded additive stretch requirement only for a subset of pairs [12]. The high-level idea of this procedure 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 every vertex with a sufficiently high degree (termed hereafter a heavy vertex) 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 π s, t ( ) be an s -t shortest-path between a source s and a heavy vertex t (in our constructions, all heavy vertices are clustered). We divide the failing events on π s, t ( ) into two classes depending on the position of the failing vertex on π s, t ( ) with respect to the least common ancestor (LCA) glyph[lscript] ( s, t ) of t 's cluster members in the BFS tree rooted at s . Specifically, a vertex fault π s, t ( ) that occurs on glyph[lscript] ( 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 π s, x ( ) between s and some member x in the cluster of t whose failing vertex v does not appear on its π s, x ( ) path. The approximate replacement path will follow π s, x ( ) and then use the intercluster path between x and t . The main technicality is when concerning the complementary case when that failing events occur strictly above glyph[lscript] ( 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 candidate to be bought by the path-buying procedure. Essentially, the structure of these paths and the cost and value functions assigned to them would guarantee that the resulting structure is sparse, and in addition, that paths that were not bought have an alternative safe path in the surviving part of the structure.

Contributions. This paper provides the first constructions for additive spanners resilient upon 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.

The main technical contribution of our algorithms is in adapting the path-buying strategy to the vertex failure setting. Such an adaptation has been initiated in [18] 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, [18] 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.1 (2-additive FT-spanner) For every n -vertex graph G = ( V, E ) , there exists a (polynomially constructible) subgraph H ⊆ G of size ˜ O n ( 5 3 / ) such that dist( s, t, H \{ v } ) ≤ dist( s, t, G \ { v } ) + 2 for every s, t, v ∈ V .

Theorem 1.2 (6-additive FT-spanner) For every n -vertex graph G = ( V, E ) , there exists a (polynomially constructible) subgraph H ⊆ G of size ˜ O n ( 3 2 / ) such that dist( s, t, H \{ v } ) ≤ dist( s, t, G \ { v } ) + 6 for every s, t, v ∈ V .

Theorem 1.3 (8-additive sourcewise FT-spanner) For every n -vertex graph G = ( V, E ) and a subset of sources S ⊂ V where | S | = ˜ O n ( 1 3 / ) , there exists a (polynomially constructible) subgraph H ⊆ G of size ˜ O n ( 4 3 / ) such that dist( s, t, H \ { v } ) ≤ dist( s, t, G \ { v } ) + 8 for every s ∈ S and t, v ∈ V .

## 2 Preliminaries

Notation. Given a graph G = ( V, E ), a vertex pair s, t and an edge weight function W : E G ( ) → 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 . 1 Hence, SP s,t, G , W ( ′ ) contains a single path for every s, t ∈ V and for every subgraph G ′ ⊆ 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 π s, t ( ) = SP s,t, G, W ( ). To avoid cumbersome notation, we may omit W and simply refer to π s, t ( ) = SP s,t, G, W ( ). For a subgraph G ′ ⊆ 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 ) = ⋃ t ∈ V π s, t ( ) be a shortest paths (or BFS) tree rooted at s . For a set S ⊆ V of source nodes, let T 0 ( S ) = ⋃ s ∈ S T 0 ( s ) be a union of the single source BFS trees. For a vertex t ∈ V and a subset of vertices V ′ ∈ V , let T t, V ( ′ ) = ⋃ u ∈ V ′ π u, t ( ) be the union of all { } × t V ′ shortest-paths (by the uniqueness of W T t,V , ( ′ ) is a subtree of T 0 ( )). t Let Γ( v, G ) be the set of v 's neighbors in G . Let E v, G ( ) = { ( u, v ) ∈ E G ( ) } be the set of edges incident to v in the graph G and let deg ( v, G ) = | E v, G ( ) | denote the degree of node v in G . For a given graph G = ( V, E ) and an integer ∆ ≤ n , a vertex v is ∆-heavy if deg ( v, G ) ≥ ∆, otherwise it is ∆-light . When ∆ 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 ∆ ≤ n , let V ∆ = { v | deg ( v, G ) ≥ ∆ } be the set of ∆-heavy vertices in G . (Throughout, we sometimes simplify notation by omitting parameters which are clear from the context.) For a subgraph G ′ = ( V , E ′ ′ ) ⊆ G (where V ′ ⊆ V and E ′ ⊆ E ) and a pair of vertices u, v ∈ V , let dist( u, v, G ′ ) denote the shortest-path distance in edges between u and v in G ′ . For a path P = [ v , . . . , v 1 k ], let LastE ( P ) be the last edge of P , let | P | denote its length and let P v , v [ i j ] be the subpath of P from v i to v j . For paths P 1 and P 2 , denote by P 1 ◦ P 2

1 The role of the weights W is to perturb the edge weights by letting W e ( ) = 1+ glyph[epsilon1] for a random infinitesimal glyph[epsilon1] &gt; 0.

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 ) ∈ P , let dist( s, e, P ) be the distance (in edges) between s and y on P . In addition, for an edge e = ( x, y ) ∈ T 0 ( s ), define dist( s, e ) = i if dist( s, x, G ) = i -1 and dist( s, y, G ) = i . A vertex w is a divergence point of the s -v paths P 1 and P 2 if w ∈ P 1 ∩ 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 2.1 ( ( α, β, S ) -AMBFS FT-spanners) A subgraph H ⊆ G is an ( α, β, S ) -FT-AMBFS (approximate multi-BFS) structure with respect to S if for every ( s, t ) ∈ S × V and every v ∈ V , dist( s, t, H \ { v } ) ≤ α · dist( s, t, G \ { v } ) + β .

Definition 2.2 ( ( α, β ) FT-spanners) A subgraph H ⊆ G is an ( α, β ) FT-spanner if it is an ( α, β, V ) -FT-AMBFS structure for G with respect to V .

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

FT-Clustering Graph. A subset Z ⊆ V is an FT-center set for V if every ∆heavy vertex v has at least two neighbors in Z , i.e., | Γ( v, G ) ∩ Z | ≥ 2. For every heavy vertex v ∈ V ∆ , let Z v ( ) = { z 1 ( v , z ) 2 ( v ) } be two arbitrary neighbors of v in Z . The clustering graph G ∆ ⊆ G consists of the edges connecting the ∆-heavy vertices v to their two representatives in Z as well as all edges incident to the ∆-light vertices. Formally,

$$G _ { \Delta } = \bigcup _ { v \in V _ { \Delta } } \{ ( v, z _ { 1 } ( v ) ), ( v, z _ { 2 } ( v ) ) \} \cup \bigcup _ { v \notin V _ { \Delta } } E ( v, G ).$$

The ∆heavy vertices are referred hereafter as clustered , hence every missing edge in G \ G ∆ is incident to a clustered vertex.

For every center vertex z ∈ Z , let C z be the cluster consisting of z and all the ∆-heavy vertices it represents, i.e., C z = { z } ∪ { v ∈ V ∆ | z ∈ 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 ∆ is 2.

glyph[negationslash]

For a failing vertex v and a heavy vertex t , let z v ( ) t ∈ Z t ( ) \{ } v be a cluster center of t in G \{ } v . In particular, if z 1 ( ) = t v , then z v ( ) = t z 1 ( ), t else z v ( ) = t z 2 ( ). t Let C v ( ) be the cluster centered t at z v ( ). t Note that since every heavy 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 2.3 (1) | E G ( ∆ ) | = O (∆ · n ) .

- (2) Every missing edge is incident to a clustered vertex in V ∆ .
- (3) The diameter of every cluster C z is 2 .
- (4) There exists an FT-center set Z ⊆ V of size | Z | = ˜ O n/ ( ∆) .

Obs. 2.3(4) follows by a standard hitting set argument.

Replacement Paths. For a source s , a target vertex t and a vertex v ∈ G , a replacement path is the shortest s -t path P s,t,v ∈ SP s,t, G ( \ { v } ) that does not go through v .

Observation 2.4 Every path P s,t,v contains at most 3 n/ ∆ ∆ -heavy vertices.

Proof: Note that

$$3 n \, \geq \, 3 \cdot \left | \bigcup _ { x \in P _ { s, t, v } \cap V _ { \Delta } } \Gamma ( x, G \, \{ v \} ) \right | \geq \sum _ { x \in P _ { s, t, v } \cap V _ { \Delta } } \deg ( x, G \, \{ v \} ) \geq | P _ { s, t, v } \cap V _ { \Delta } | \cdot \Delta$$

where the second inequality follows by the fact the every vertex u ∈ V \{ } v has at most 3 neighbors on P s,t,v . The observation follows.

New-ending replacement paths . Areplacement path P s,t,v is called new-ending if its last edge is different from the last edge of the shortest path π 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 π s, t ( ) at the vertex b , it joins π s, t ( ) again only at the final vertex t . It is shown in [17] that for a given graph G and a set S of source vertices, a structure H ⊆ G containing a BFS tree rooted at each s ∈ S plus the last edge of each new-ending replacement path P s,t,v for every ( s, t ) ∈ S × V and every v ∈ V , is an FT-MBFS structure with respect to S . Our algorithms exploit the structure of new-ending replacement paths to construct ( β, S )-additive FT-spanners. Essentially, a key section 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 π s , t ( ′ ) \{ } t for some other source s ′ ∈ S .

The basic building block. Our constructions of β -additive FT-spanners, for β ≥ 2, consist of the following two building blocks: (1) an FT-clustering graph G ∆ for some parameter ∆, and (2) an ( β -2 , Z )-additive FT-spanner where Z is an FT-center set (i.e., cluster centers) for the vertices.

Lemma 2.5 Let β ≥ 2 and H = G ∆ ∪ H β -2 ( Z ) where Z is an FT-center set for V ∆ . Then H is an β additive FT-spanner.

Proof: Consider vertices u , u 1 2 , u 3 ∈ V . Let P ∈ SP u ,u ,G ( 1 2 \ { u 3 } ) be the u 1 -u 2 replacement path in G \ { u 3 } and let ( x, y ) be the last missing edge on P \ H (i.e., closest to u 2 ). Since G ∆ ⊆ H , by Obs. 2.3(2), y is a clustered vertex. Let z = z u 3 ( y ) be the cluster center of y in G \ { u 3 } , and consider the following u 1 -u 2 path P 3 = P 1 ◦ P 2 where P 1 ∈ SP u ,z,H ( 1 \ { u 3 } ) and P 2 = ( z, y ) ◦ P y, u [ 2 ]. Clearly, P 3 ⊆ H \{ u 3 } , so it remains to bound its length. Since H β -2 ( Z ) ⊆ H , it holds that | P 1 | ≤ dist( u , z, G 1 \ { u 3 } ) + β -2. Hence,

$$\text{dist} ( u _ { 1 }, u _ { 2 }, H \, \langle \{ u _ { 3 } \} ) & \ \leq \ \ | P _ { 3 } | \ = \ | P _ { 1 } | + | P _ { 2 } | \\ & \ \leq \ \text{dist} ( u _ { 1 }, z, G \, \langle \{ u _ { 3 } \} ) + \beta - 2 + \text{dist} ( y, u _ { 2 }, G \, \langle \{ u _ { 3 } \} ) \\ & \ \leq \ \text{dist} ( u _ { 1 }, y, G \, \langle \{ u _ { 3 } \} ) + \text{dist} ( y, u _ { 2 }, G \, \langle \{ u _ { 3 } \} ) + \beta \\ & \ \leq \ \ | P | + \beta \ = \ \text{dist} ( u _ { 1 }, u _ { 2 }, G \, \langle \{ u _ { 3 } \} ) + \beta$$

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

## 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 [17].

Fact 3.1 ([17]) There exists a polynomial time algorithm that for every n -vertex graph G = ( V, E ) and source set S ⊆ V constructs an FT-MBFS structure H S 0 ( ) from each source s i ∈ S , tolerant to one edge or vertex failure, with a total number of O ( √ | S | · n 3 2 / ) edges.

Set ∆ = glyph[ceilingleft] n 2 3 / glyph[ceilingright] and let Z be an FT-center set for V ∆ as given by Obs. 2.3(4). Let H Z 0 ( ) be an FT-MBFS structure with respect to the source set Z as given by Fact 3.1. Then, let H = G ∆ ∪ H Z . 0 ( ) Thm. 1.1 follows by Lemma 2.5, Obs. 2.3 and Fact 3.1.

## 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 ⊆ V . The single source case (where | S | = 1) is considered in [18], which provides a construction of a single source FT-spanner 2 with O n ( 4 3 / ) edges and additive stretch 4. The current construction increases the stretch to 8 to provide 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

Lemma 4.1 There exists a subgraph H S 4 ( ) ⊆ G with ˜ O (max {| S | · n, ( n/ S | | ) 3 } ) edges satisfying dist( s, t, H 4 ( S ) \ { v } ) ≤ dist( s, t, G \ { v } ) + 4 for every ( s, t ) ∈ S × V and v ∈ V .

The following notation is useful in our context. Let C = { C z | z ∈ Z } be the collection of clusters corresponding to the FT-centers Z . For a source s ∈ S and a cluster C z ∈ C rooted at FT-center z ∈ Z , let 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 π s, C ( z ) be the path connecting s and LCA ( s, C z ) in T 0 ( s ).

## 4.1.1 Algorithm Cons4SWSpanner for constructing H S 4 ( ) spanner

Step (0): Replacement-path definition. For every ( s, t ) ∈ S × V and every v ∈ V , let P s,t,v = SP s,t, G ( \ { v } , W ).

Step (1): Clustering. Set ∆ = | S | and let Z ⊆ V be an FT-center set of size ˜ O n/ ( ∆) (by Obs. 2.3(4) such set exists). Let C = { C z | z ∈ Z } be the collection of | Z | clusters. For a heavy vertex t , let C 1 ( ) t , C 2 ( ) be its two clusters in t C corresponding to the centers z 1 ( ) and t z 2 ( ) respectively. t

2 The construction of [18] supports a single edge failure, yet, it can be modified to overcome a single vertex failure as well.

Step (2): Shortest-path segmentation. For every ( s, t ) ∈ S × V ∆ , the algorithm uses the first cluster of t , C 1 ( ), to segment the path t π s, t ( ). Define

$$\pi ^ { f a r } ( s, t ) = \pi ( s, \ell ( s, t ) ) \, \sum \{ \ell ( s, t ) \} \ \text{ and } \ \pi ^ { n e a r } ( s, t ) = \pi ( \ell ( s, t ), t ) \, \sum \{ \ell ( s, t ) \},$$

where glyph[lscript] ( s, t ) = LCA ( s, C 1 ( )) t is the LCA of the cluster C 1 ( ) t in the tree T 0 ( s ). Hence, π s, t ( ) = π far ( s, t ) ◦ glyph[lscript] ( s, t ) ◦ π near ( s, t ). The algorithm handles separately vertex faults in the near and far segments. Let V near ( s, t ) = V ( π near ( s, t )) and V far ( s, t ) = V ( π far ( s, t )).

## Step (3): Handling faults in the cluster center and the LCA. Let

$$E ^ { l o c a l } ( t ) = \{ \text{Last} \, E ( P _ { s, t, v } ) \ | \ s \in S, v \in \{ z _ { 1 } ( t ), \text{LCA} ( s, C _ { 1 } ( t ) ) \} \} \text{ and } E ^ { l o c a l } = \bigcup _ { t \in V _ { \Delta } } E ^ { l o c a l } ( t ),$$

be the last edges of replacement-paths protecting against the failure of the primary cluster center z 1 ( ) and the least common ancestor t LCA ( s, C 1 ( )). t

Step (4): Handling far vertex faults V far ( s, t ) . A replacement path P s,t,v is new-ending if its last edge is not in ( T 0 ( S ) ∪ G ∆ ). For a new-ending path P s,t,v , let b s,t,v be the unique divergence point of P s,t,v from π s, t ( ) (in the analysis we show that such point exists). 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 \{ b s,t,v } denote the detour segment excluding the divergence point. For every clustered vertex t , let P far ( ) be the collection of new-ending t s -t paths protecting against vertex faults in the far segments, i.e., P far ( ) = t { P s,t,v | s ∈ S, LastE ( P s,t,v ) / ∈ T 0 ( S ) and v ∈ V far ( s, t ) } .

The algorithm divides this set into two subsets P far dep ( ) and t P far indep ( ) depending on the structure t 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 π s , t ( ′ ) \ { } t for some s ′ ∈ S , i.e., for a dependent path P s,t,v , it holds that glyph[negationslash]

$$V ( D _ { s, t, v } ^ { + } ) \cap V ( T ( t, S ) ) \neq \{ t \} \.$$

Otherwise, it is independent . Let glyph[negationslash]

$$\mathcal { P } _ { d e p } ^ { f a r } ( t ) = \{ P _ { s, t, v } \in \mathcal { P } ^ { f a r } ( t ) \ | \ s \in S, v \in V ^ { f a r } ( s, t ) \text{ and } V ( D _ { s, t, v } ^ { + } ) \cap V ( T ( t, S ) ) \neq \{ t \} \}$$

be the set of all S ×{ } t dependent paths and let P far indep ( ) = t P far \P far dep ( ) be the set of independent t paths.

Step (4.1): Handling dependent new-ending paths. The algorithm simply takes the last edges E far dep ( ) of all dependent replacement paths where t E far dep ( ) = t { LastE ( P ) | P ∈ P far dep ( ) t } . (In the analysis section, we show that the E far dep ( ) sets are sparse.) t Let E far dep = ⋃ t ∈ V ∆ E far dep ( ). t

Step (4.2): Handling independent new-ending paths. The algorithm employs a modified path-buying procedure on the collection P far indep = ⋃ t ∈ V ∆ P far indep ( ) of new-ending independent paths. t The paths of P far indep are considered in some arbitrary order. A path P ∈ P far indep is bought, if it improves the pairwise cluster distances in some sense. Starting with

$$G _ { 0 } = T _ { 0 } ( S ) \cup G _ { \Delta } \cup E ^ { l o c a l } \cup E ^ { f a r } _ { d e p }$$

at step τ ≥ 0, the algorithm is given G τ ⊆ G and considers the path P τ = P s,t,v . Let e = ( x, y ) be the first missing edge on P τ \ E G ( τ ) (where x is closer to s ). Note that since G ∆ ⊆ 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 ) ∈ Z u ( ) \{ } v . For every cluster C , let V f ( C ) be the collection of vertices appearing on the paths π s, C ( ) = π s, ( LCA ( s, C )) for every s ∈ S excluding the vertices of the clusters. That is,

$$V _ { f } ( C ) = \bigcup _ { s \in S } V ( \pi ( s, C ) ) \, \langle \, C.$$

The path P τ is added to G τ resulting in G τ +1 = G τ ∪ P τ , only if

$$\text{dist} ( x, t, P _ { \tau } ) < \text{dist} ( C _ { v } ( x ), C _ { v } ( t ), G _ { \tau } \, \langle V _ { f } ( C _ { v } ( t ) ) ).$$

Let τ ′ = |P far indep | be the total number of independent paths considered to be bought by the algorithm. Then, the algorithm outputs H S 4 ( ) = G . τ ′ This completes the description of the algorithm.

Analysis. Throughout the discussion, we consider a P s,t,v paths of clustered vertices t ∈ V ∆ . A path P s,t,v is a new-ending path, if LastE ( P s,t,v ) / G ∈ 0 (see Eq. (2)). Let b s,t,v be the first divergence point of P s,t,v and π s, t ( ).

Lemma 4.2 For every vertex u ∈ P s,t,v such that LastE ( P s,t,v [ s, u ]) / T ∈ 0 ( S ) , it holds that: (a) v ∈ π s, u ( ) . (b) V ( P s,t,v [ b s,t,v , u ]) ∩ V ( π 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 ( \ { v } , W ) = π s, u ( ). Leading to contradiction to the fact that 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 π s, t ( ) above the failing vertex v . Since by Lemma 4.2, v ∈ π s, u ( ), it also holds that b s,t,v ∈ π s, u ( ). Assume towards contradiction that there exists an additional point

$$w \in ( P _ { s, t, v } [ b _ { s, t, v }, u ] \cap \pi ( s, u ) ) \, \langle \{ b _ { s, t, v }, u \}.$$

There are two cases to consider (b1) v ∈ π b ( s,t,v , w ), in such a case, v / π w, u ∈ ( ) and hence π w, u ( ) = SP w,u,G ( \ { v } ) = P s,t,v [ w,u ], contradiction that LastE ( P s,t,v [ s, u ]) / T ∈ 0 ( S ). (b2) v ∈ π w, u ( ). In such a case, v / ∈ π b ( s,t,v , w ) and hence π b ( s,t,v , w ) = SP b ( s,t,v , w, G \ { v } ) = P s,t,v [ b s,t,v , w ], contradiction to the fact the b s,t,v is a divergence point from π s, t ( ). The claim holds.

The next claim 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 ˜ P s,t,v in T 0 ∪ G ∆ .

Lemma 4.3 If LastE ( P s,t,v ) / G ∈ 0 and v ∈ π near ( s, t ) , then dist( s, t, ( G 0 ∪ G ∆ ) \{ } v ) ≤ dist( s, t, G \ { v } ) + 4 .

glyph[negationslash]

glyph[negationslash]

Proof: Since v ∈ π near ( s, t ), i.e., the failing vertex occurs strictly below LCA ( s, C 1 ( )) t on π s, t ( ), there exists a vertex w ∈ C 1 ( ) t such that v / π s, w ∈ ( ) (hence in particular w = v ). See Fig. 1. Since LastE ( P s,t,v ) / ∈ E local , it holds that v = z 1 ( ). t Consider the following s -w path P = π s, w ( ) ◦ [ w,z 1 ( ) t , t ]. Clearly, P ⊆ ( T 0 ( S ) ∪ G ∆ ) \ { v } . By the triangle inequality, as the diameter of the cluster C 1 ( ) is 2, it holds that t dist( s, t, ( T 0 ( S ) ∪ G ∆ ) \ { v } ) ≤ dist( s, w, G ) + 2 ≤ dist( s, t, G ) + 4 ≤ dist( s, t, G \ { v } ) + 4 .

Figure 1: Handling near vertex faults. Schematic illustration of an approximate replacement path in ( T 0 ∪ G ∆ ) \{ } v . Shown is an π s, t ( ) whose failing vertex v occurs strictly below the least common ancestor LCA ( s, C 1 ( )). t The alternative replacement path exploits the surviving π s, w ( ) ⊆ T 0 ( S ) path for w ∈ C 1 ( ) and the intracluster path connecting t w and v through z = z v ( ). t

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0409v1-figure-419e3f68-43c8-40d7-9cd6-33a7a55189f1.jpg)

The claim follows.

For every new-ending path P s,t,v , recall that D + s,t,v = D s,t,v \ { b s,t,v } . Let ( x, y ) be the first missing in P s,t,v \ G 0 (where x is closer to y ). The following auxiliary claims are useful.

Lemma 4.4 For every vertex u ∈ P s,t,v such that LastE ( P s,t,v [ s, u ]) / ∈ G 0 , it holds that: (a) C v ( u ) = C 1 ( u ) . (b) P s,t,v [ x, t ] ⊆ D + s,t,v .

glyph[negationslash]

glyph[negationslash]

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 ( \ { v } , W ). Since LastE ( P s,t,v [ s, u ]) / E ∈ local , it holds that v = 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 = b , which implies the claim. By 4.2, v ∈ π s, y ( ). Since b appears above v on π s, t ( ), b is mutual to π s, t ( ) and π s, y ( ). Hence, the s -y shortest path has the following form: π s, y ( ) = π s, b ( ) ◦ π b, v ( ) ◦ π v, y ( ). Since b = v = y , dist( y, b, G ) ≥ 2, and hence also dist( y, b, G \ { v } ) ≥ 2, concluding that b = x . The lemma follows.

glyph[negationslash]

glyph[negationslash]

glyph[negationslash]

Corollary 4.5 Let t ∈ V ∆ . For every P s,t,v ∈ P far indep ( ) t , P s,t,v [ x, t ] ∩ V f ( C v ( )) = t ∅ 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 ∩ T t, S ( ) = { } t . Since t ∈ C v ( ), t by Eq. (3), t / V ∈ f ( C v ( )) and hence t D + s,t,v ∩ V f ( C v ( )) = t ∅ . The corollary follows by combining with Lemma 4.4(b).

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

Lemma 4.6 H S 4 ( ) is a (4 , S ) FT-spanner.

Proof: Let H = H S 4 ( ). The proof is by contradiction. Assume that there exists a vertex s ∈ S , a target vertex t and a failing vertex v such that dist( s, t, H \ { v } ) &gt; dist( s, t, G \ { v } ) + 4. Let

$$B P = \{ ( t, v ) \ | \ t \in V, v \in ( V \cup \{ \emptyset \} ) \ \text{ and} \\ \text{dist} ( s, t, H \, \searrow \{ v \} ) > \text{dist} ( s, t, G \, \searrow \{ v \} + 4 \}$$

glyph[negationslash]

be the set of 'bad pairs' namely, vertex pair ( t, v ) whose additive stretch in H is greater than 4 with respect to s ∈ S . By the contradictory assumption BP = ∅ . Since the BFS tree T 0 ( s ) is in H , it holds that the failing vertex v ∈ π s, t ( ) for every pair ( t, v ) ∈ BP .

For every bad pair ( t, v ) ∈ BP define e t,v to be the last missing edge of P s,t,v = SP s,t, G ( \ { v } , W ) in H . Let d t, v ( ) = dist( s, e t,v , P s,t,v ) be the distance of the last missing edge from s on P s,t,v . Finally, let ( t 0 , v 0 ) ∈ BP be the pair that minimizes d t, v ( ), and let ee t 0 ,v 0 = ( u, t i ). Note that e t 0 ,v 0 is the shallowest 'deepest missing edge' over all bad pairs ( t, v ) ∈ BP .

## Lemma 4.7 The pair ( t , v i 0 ) ∈ BP .

Proof: Assume towards contradiction that ( t , v i 0 ) / BP ∈ and let P ′′ ∈ SP s,t , H ( i \ { v 0 } ). Hence, since ( t , v i 0 ) / BP ∈ , it holds that

$$| P ^ { \prime \prime } | \ & \leq \ \text{dist} ( s, t _ { i }, G \, \langle v _ { 0 } \} ) + 4 \\ & = \ \ | P _ { s, t _ { 0 }, v _ { 0 } } [ s, t _ { i } ] | + 4.$$

We now consider the following s -t 0 replacement path Q = P ′′ ◦ P s,t 0 ,v 0 [ t , t i 0 ]. By definition of ( t , v i 0 ) (last missing edge on P s,t i ,v 0 ), Q ⊆ H \ { v 0 } . In addition,

$$| Q | \ & = \ | P ^ { \prime \prime } | + | P _ { t _ { 0 }, v _ { 0 } } [ t _ { i }, t _ { 0 } ] | \leq | P _ { s, t _ { 0 }, v _ { 0 } } [ s, t _ { i } ] | + 4 + | P _ { s, t _ { 0 }, v _ { 0 } } ( t _ { i }, t _ { 0 } ) | \\ & = \ | P _ { s, t _ { 0 }, v _ { 0 } } | + 4 \ = \ \text{dist} ( s, t _ { 0 }, G \, \langle v _ { 0 } \} ) + 4$$

where the inequality follows by Eq. (5). This contradicts the fact that ( t 0 , v 0 ) ∈ BP .

Since π s, t ( i ) ⊆ H , by the fact that ( t , v i 0 ) ∈ BP , we have that the failing vertex v 0 occurs on the shortest-path π s, t ( i ). Since the last edge of P s,t i ,v 0 = P s,t 0 ,v 0 [ s, t i ] is missing, by the fact that the clustering graph G ∆ is in H , by Obs. 2.3(2), it holds that t i is clustered (i.e., t i ∈ V ∆ ). By step (2), since E local ⊆ H , it holds that v 0 / ∈ { z 1 ( t i ) , LCA ( s, C 1 ( t i )) } . Combining with Lemma 4.3, it holds that v 0 / V ∈ near ( s, t i ). Hence, v 0 ∈ V far ( s, t i ). There are further two cases. Case (1) P s,t i ,v 0 is dependant. By step (4.1), we then have that LastE ( P s,t i ,v 0 ) ∈ E far dep ( ), contradiction to the fact t that LastE ( P s,t i ,v 0 ) is missing in H .

Consider case(2) where P s,t i ,v 0 is an independent path, i.e., P s,t i ,v 0 ∈ P far indep ( ) and hence it was t considered to be bought in the path-buying procedure of Step (4.2). By the fact that the pair ( t , v i 0 ) is a bad pair (i.e., ( t , v i 0 ) ∈ BP ), we conclude that the algorithm did not buy the path. Let τ be the iteration at which P τ = P s,t i ,v 0 was considered to be purchased in the path-buying procedure. Let G τ be the current spanner in iteration τ . Let x be the vertex incident to the first missing edge on P τ \ E G ( τ ).

Let C 0 = C v 0 ( t i ) be the cluster of t i in G ∆ \ { v 0 } . Since LastE ( P τ ) / E ∈ local , by Lemma 4.4(a) C 0 = C 1 ( t i ) and z v 0 ( t i ) = z 1 ( t i ). By definition,

$$v _ { 0 } \in \pi ^ { f a r } ( s, t _ { i } ) = \pi ( s, C _ { 0 } ) \, \wedge \, \{ \text{LCA} ( s, C _ { 0 } ) \}.$$

Hence, in particular failing vertex is not in the cluster C 0 , i.e., v 0 / C ∈ 0 and by Eq. (3),

$$v _ { 0 } \in V _ { f } ( C _ { 0 } ).$$

Since P τ was not bought by the algorithm, by Eq. (4), we have that

$$\text{dist} ( C _ { v _ { 0 } } ( x ), C _ { 0 }, G _ { \tau } \, \sum V _ { f } ( C _ { 0 } ) ) \leq \text{dist} ( x, t _ { i }, P _ { \tau } ).$$

Let w 1 ∈ C v 0 ( x ) and w 2 ∈ C 0 be an arbitrary closest pair in G τ \ V f ( C 0 ) from the clusters C v 0 ( x ) and C 0 respectively satisfying that dist( w , w , G 1 2 τ \ V f ( C 0 )) = dist( C v 0 ( x , C ) 0 , G τ \ V f ( C 0 )).

glyph[negationslash]

Let z 1 (resp., z 2 ) be the cluster center of C v 0 ( x ) (resp., C 0 ). Consider the following s -t i replacement path in H \ { v 0 } , P 5 = P 1 ◦ P 2 ◦ P 3 ◦ P 4 where P 1 = P τ [ s, x ], P 2 = [ x, z 1 , w 1 ] and P 3 ∈ SP w ,w ,G ( 1 2 τ \ V f ( C 0 )) and P 4 = [ w , z 2 2 , t i ]. For an illustration see Fig. 2. We first claim that P 5 ⊆ H \ { v 0 } . Since x incident to the first missing edge on P τ , P 1 is in H \ { v 0 } . By Eq. (6), v 0 ∈ V f ( C 0 ) and since w , w 1 2 ⊆ G τ \ V f ( C 0 ) it also holds that w , w 1 2 = v 0 . Finally note that G ,G τ ∆ ⊆ H , hence P , P 2 4 ⊆ H \ { v 0 } . We next bound the length of P 5 .

$$\text{dist} ( s, t _ { i }, H \, \{ v _ { 0 } \} ) \ & \ \leq \ \ P _ { 5 } \ \leq \ \text{dist} ( s, x, G \, \{ v _ { 0 } \} ) + 2 + \text{dist} ( w _ { 1 }, w _ { 2 }, G _ { \tau } \, \| \vee \| _ { f } ( C _ { 0 } ) ) + 2 \\ & \ \leq \ \text{dist} ( s, x, G \, \{ v _ { 0 } \} ) + \text{dist} ( C _ { v _ { 0 } } ( x ), C _ { 0 }, G _ { \tau } \, \| \vee \| _ { f } ( C _ { 0 } ) ) + 4 \\ & \ \leq \ \text{dist} ( s, x, G \, \{ v _ { 0 } \} ) + \text{dist} ( x, t _ { i }, P _ { \tau } ) + 4 \\ & \ \leq \ \left | P _ { s, t _ { i }, v } \right | + 4 = \text{dist} ( s, t _ { i }, G \, \{ v _ { 0 } \} ) + 4, \\ \quad.. \ \quad \..$$

where Eq. (8) follows by Eq. (7). We end with contradiction to the fact that the pair ( t , v i 0 ) is a bad pair. The claim follows.

Size analysis of H S 4 ( ) . We proceed with the size analysis.

$$\text{Lemma } 4. 8 \text{ for every } t \in V _ { \Delta }, \, | E ^ { l o c a l } ( t ) | = O ( | S | ), \, \text{ hence } | E ^ { l o c a l } | = O ( | S | \cdot n ).$$

Bounding the number of last edges in E far 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 π far ( s, t ). To bound the number of edges in E far dep ( ), t consider the partial BFS tree rooted at t , T t, S ( ) ⊆ T 0 ( T ), whose leaf set is contained in the vertex set S where T t, S ( ) = ⋃ s ∈ S π 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 ∪ { u ∈ T t, S ( ) | deg ( u, T ( t, S )) ≥ } 3 , be the union of S and the vertices with degree at least 3 in the tree T t, S ( ). We have that | V + | &lt; 2 | S | . A pair of vertices x, y ∈ V + is adjacent if their shortest-path π x, y ( ) is contained in the tree T t, S ( ) and it is free from any other V + vertex, i.e, π x, y ( ) ⊆ T t, S ( ) and π x, y ( ) ∩ V + = { x, y } . Let Π( V + ) = { π x, y ( ) | x, y ∈ V + and x, y are adjacent } be the collection of paths between adjacent pairs.

Observation 4.9 (1) T t, S ( ) = Π( V + ) . (2) Π( V + ) consists of at most 2 | S | +1 paths π x, y ( ) (i.e., there are at most 2 | S | adjacent pairs).

4-additive sourcewise  FT-spanner.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0409v1-figure-31e1ebf4-0a1a-4e8e-879e-fbd19c75c8d0.jpg)

Figure 2: Schematic illustration of the path-buying procedure of Alg. Cons4SWSpanner . Shown is an s -t path P τ = P s,t,v considered to be bought in time τ . The green paths correspond to shortest-paths in T 0 ( s ) and the red edges correspond to missing edges on P τ \ E G ( τ ). The first missing edge on P τ \ E G ( τ ) is incident to x . If P τ was not bought, then there exists a short route between a pair of vertices w 1 and w 2 belonging to C v ( x ) and C v ( ) (respectively) in t H \ { v } .

We now show the following.

Lemma 4.10 For every t ∈ V ∆ , | E far dep ( ) t | = O S ( | | ) .

We first claim that every two dependent replacement paths with the same divergence point have the same last edge.

Lemma 4.11 For every two dependent paths P s 1 ,t,v 1 , P s 2 ,t,v 2 ∈ P far dep ( ) t , if b s 1 ,t,v 1 = b s 2 ,t,v 2 then LastE ( P s 1 ,t,v 1 ) = LastE ( P s 1 ,t,v 2 ) .

Proof: Let b = b s 1 ,t,v 1 = b s 2 ,t,v 2 . Since b ∈ π s , t ( 1 ) ∩ π s , t ( 2 ) it holds that π s , t ( i ) = π s , b ( i ) ◦ π b, t ( ) for i ∈ { 1 2 , } . In addition, since P s ,t,v i i [ s , b i ] = π s , b ( i ) for i ∈ { 1 2 , } , it holds that both failing vertices v 1 and v 2 occur in the common segment π b, t ( ). Recall that P s ,t,v i i is a newending path, hence by the definition of the divergence point b (see Lemma 4.2(b)), it holds that V ( P s ,t,v i i [ b, t ]) ∩ V ( π 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 1 ,t,v 1 [ b, t ] = SP b,t, G ( \ { v , v 1 2 } ). We get that LastE ( P s 1 ,t,v 1 ) = LastE ( P s 2 ,t,v 2 ) as needed.

Since our goal is to bound the number of last edges of the new ending dependent paths P far dep ( ), t to avoid double counting, we now restrict attention to Q far ( ), a collection of representative paths in t P far dep ( ) each ending with a distinct new edge from t E far dep ( ). t Formally, for each new edge e ∈ E far dep ( ), t let P e ( ) be an arbitrary path in P far dep ( ) satisfying that t LastE ( P e ( )) = e . Let Q far ( ) = t { P e , e ( ) ∈ E far dep ( ) t } (hence |Q far ( ) t | = | E far dep ( ) ). t | From now on, we aim towards bounding the cardinality of

Q far ( ). t Let DP = { b s,t,v | P s,t,v ∈ Q far ( ) t } be the set of divergence points of the new ending paths in Q far ( ). t By Lemma 4.11, it holds that in order to bound the cardinality of P far dep ( ), it t is sufficient to bound the number of distinct divergence points. To do that, we show that every path π x, y ( ) of two adjacent vertices x, y ∈ V + , contains at most one divergence point in DP \ V + .

## Lemma 4.12 | π x, y ( ) ∩ ( DP \ V + ) | ≤ 1 for every π x, y ( ) ∈ Π( V + ) .

glyph[negationslash]

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 π x, y ( ) for two adjacent vertices x, y ∈ V + . For ease of notation, let P i = P s ,t,v i i , b i = b s ,t,v i i , D i = D s ,t,v i i and D + i = D i \ { b i } for i ∈ { 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 ( ) ⊆ T t, S ( ). For an illustration see Fig. 3. We now claim that the failing vertices v , v 1 2 occur on π y, t ( ). Since D + 1 and D + 2 are vertex disjoint with π y, t ( ) \{ } 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 LastE ( P 1 ) , LastE ( P 2 ) could have been avoided. We now focus on v 1 and show that v 1 ∈ π 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 ∈ s \ { s 1 } satisfying that ( D + 1 ∩ π s , t ( 3 ) ) \ { } glyph[negationslash] t = ∅ . Let w ∈ ( D + 1 ∩ π s , t ( 3 ) ) \{ } 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 the subtree T x ( ) ⊆ T t, S ( ) rooted at x . To see why this holds, assume, towards contradiction, that s 3 ∈ T x ( ). It then holds that the replacement path P 1 has the following form P 1 = π s , x [ 1 ] ◦ π x, b ( 1 ) ◦ P 1 [ b 1 , w ] ◦ P 1 [ w,t ]. Recall, that since b 1 ∈ DP \ V + , b 1 = x and also b 1 = w . Since P 1 [ x, w ] goes through b 1 , by the optimality of P 1 , it holds that glyph[negationslash]

$$\text{dist} ( x, w, G \, \sum \{ v _ { 1 } \} ) > \text{dist} ( b _ { 1 }, w, G \, \sum \{ v _ { 1 } \} ) \.$$

glyph[negationslash]

On the other hand, the path π s , t ( 3 ) has the following form: π s , t ( 3 ) = π s , w ( 3 ) ◦ π w, x ( ) ◦ π x, b ( 1 ) ◦ π b , t ( 1 ). Hence, π w, b ( 1 ) goes through x . Since the failing vertex v 1 ∈ π b , t ( 1 ) is not in π w, b ( 1 ), by the optimality of π w, b ( 1 ), we get that dist( w,b , G 1 \ { v 1 } ) &gt; dist( x, w, G \ { v 1 } ), leading to contradiction with Ineq. (9). Hence, we conclude that s 3 / T ∈ ( x ) (in particular this implies that s 3 = s 2 ). Note that π w, t ( ) is a segment of π s , t ( 3 ) and hence it is contained in the tree T t, S ( ). Since P 1 is a new-ending path (i.e., LastE ( P 1 ) / ∈ T t, S ( )), we have that P 1 [ w,t ] = π w, t ( ) are distinct w -t paths. We next claim that the failing vertex v 1 must occur on π w, t ( ) and hence also on π s , t ( 3 ). To see this, observe that if π w, t ( ) would have been free from the failing vertex v 1 , then it implies that π w, t ( ) = SP w,t,G ( \{ v 1 } ) = P 1 [ w,t ], contradiction as LastE ( P 1 ) = LastE ( π w, t ( )). Finally, we show that v 1 ∈ π y, t ( ). By the above, the failing vertex v 1 is common to both paths π s , t ( 1 ) and π s , t ( 3 ), i.e., v 1 ∈ π s , t ( 1 ) ∩ π s , t ( 3 ). By the definition of the path π x, y ( ), all its internal vertices u have degree 2 and hence ( π x, y ( ) ∩ π s , t ( 3 )) \{ } y = ∅ , concluding that v 1 ∈ π y, t ( ). By the same argumentation, it also holds that v 2 is in π y, t ( ). As the detours D 1 and D 2 are vertex disjoint with π y, t ( ) \ { } t , it holds that they are free from the two failing vertices, i.e., v , v 1 2 / D ∈ 1 ∪ D 2 . Since P , P 1 2 ∈ Q far ( ), it holds that t LastE ( P 1 ) = LastE ( P 2 ), and hence there are two b 1 -t distinct shortest paths in G \{ v , v 1 2 } , given by D 1 and π b , b ( 1 2 ) ◦ 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.

glyph[negationslash]

glyph[negationslash]

glyph[negationslash]

By Lemma 4.11 there are at most | V + | replacement paths with divergence point in V + . By Lemma 4.12, there is at most one divergence point on each segment π x, y ( ) of an adjacent pair ( x, y ). Combining with Obs. 4.9(2), we get | E far ( ) t | = |Q far ( ) t | = O S ( | | ). The lemma follows.

Figure 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 newending s 1 -t dependant path P s 1 ,t,v 1 with a divergence point b 1 ∈ π x, y ( ) intersects with π s , t ( 3 ) at the vertex w / ∈ { 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 π w, t ( ). Hence v 1 ∈ π s , t ( 1 ) ∩ π s , t ( 3 ), implying that v 1 ∈ π y, t ( ). Since this holds for any new-ending path with a divergence point in π x, y ( ), we get that only one new edge from all these paths is needed.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0409v1-figure-aa35cd40-79b9-4234-83e2-37d232a3f0fc.jpg)

We complete the size analysis and proves Lemma 4.1, 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).

$$\text{Lemma } 4. 1 3 \ | H _ { 4 } ( S ) \, \sum G _ { 0 } | = \widetilde { O } ( ( n / | S | ) ^ { 3 } ).$$

Proof: Let B ⊆ P far indep ( ) be the set of paths bought in the path-buying procedure of Step (4.2). t For every ordered pair of clusters C , C 1 2 ∈ C , let B ( C , C 1 2 ) ⊆ B be the set of paths that were added since they improved the distance of C 1 and C 2 , that is

$$\mathcal { B } ( C _ { 1 }, C _ { 2 } ) = \{ P _ { \tau } \in \mathcal { B } \ | \ C _ { 1 } ( \tau ) = C _ { 1 } \text{ and } C _ { 2 } ( \tau ) = C _ { 2 } \}$$

Clearly, B = ⋃ C ,C 1 2 ∈C B ( C , C 1 2 ). We next use the fact that the diameter of each cluster C ∈ C is small, to bound the cardinality of the set B ( C , C 1 2 ).

$$\text{Lemma } 4. 1 4 \ | \mathcal { B } ( C _ { 1 }, C _ { 2 } ) | \leq 5 \text{ for every } C _ { 1 }, C _ { 2 } \in \mathcal { C }.$$

Proof: Fix C , C 1 2 ∈ C and order the paths of B ( C , C 1 2 ) according to the time step they were added to the spanner B ( C , C 1 2 ) = { P τ 1 , . . . , P τ N } where τ 1 &lt; τ 2 &lt; . . . &lt; τ N where N = |B ( C , C 1 2 ) . | Since P τ k ∈ P far indep , it is a new-ending path, i.e., LastE ( P τ k ) / ∈ T 0 ( S ). Let P τ k = P s k ,t k ,v k and D τ k = D s k ,t k ,v k denote the detour segment of this path. Let x k be the vertex adjacent to the first missing edge on P τ k . Hence, C 1 = C v k ( x k ) and C 2 = C v k ( t k ) for every k ∈ { 1 , . . . , N } and also V f ( C v k ( t k )) = V f ( C 2 ) for every k ∈ { 1 , . . . , N } . Since T 0 ( S ) ⊆ G 0 , the missing edges of P τ k are restricted to the detour segment D τ k .

In addition, since P τ k ∈ P far indep , it holds that the failing vertex v k occurs on the far segment π far ( s k , t k ) and in particular, v k / C ∈ 2 (i.e., v k occurs strictly above the least common ancestor LCA ( s k , C 2 ) and since all cluster members appears on T 0 ( s k ) in the subtree rooted at LCA ( s k , C 2 ), the far segment π far ( s k , t k ) is free from cluster members). We therefore have

$$\{ v _ { 1 }, \dots, v _ { N } \} & \subseteq V _ { f } ( C _ { 2 } ) \.$$

Note that π s , C ( k 2 ) ⊆ π s , t ( k k ) and hence it is contained in T t , S ( k ) for every k ∈ { 1 , . . . , N } . By the definition of independent paths (see Eq. (1) for the definition of dependent paths), we have that

$$D _ { s _ { k }, t _ { k }, v _ { k } } ^ { + } \cap T ( t _ { k }, S ) = \left \{ t _ { k } \right \} \,.$$

Consequently, by Lemma 4.4(b),

$$P _ { \tau _ { k } } [ x _ { k }, t _ { k } ] \subseteq D _ { \tau _ { k } } ^ { + } \subseteq G \, \sum V _ { f } ( C _ { 2 } ) \.$$

glyph[negationslash]

where the last inclusion holds by the fact that t k / ∈ V f ( C 2 ) and V f ( C 2 ) ⊆ ⋃ s ∈ S π s, C ( 2 ) ⊆ ⋃ s ∈ S π s, t ( ) = T t, S ( ). Let z i ∈ Z be the cluster center of C i for i ∈ { 1 2 , } . We therefore have that z 1 = z v 1 ( x 1 ) = . . . = z v N ( x N ) and z 2 = z v 1 ( t 1 ) = . . . = z v N ( t N ) and hence z 2 = v k for every k ∈ { 1 , . . . , N } . Hence,

$$z _ { 1 }, z _ { 2 } & \notin \{ v _ { 1 }, \dots, v _ { N } \}.$$

For every k ∈ { 1 , . . . , N } , denote

$$X _ { k } = \text{dist} ( x _ { k }, t _ { k }, G _ { \tau _ { k + 1 } } \, \langle V _ { f } ( C _ { 2 } ) ).$$

We now show that X &lt; X k k -1 for every k ∈ { 2 , . . . N } .

Since the path P τ k is purchased at time τ k , we have that

$$X _ { k } \ \leq \ \text{dist} ( x _ { k }, t _ { k }, P _ { \tau _ { k } } \, \langle V _ { f } ( C _ { 2 } ) )$$

$$= \text{ dist} ( x _ { k }, t _ { k }, P _ { \tau _ { k } } )$$

$$< \text{ dist} ( C _ { 1 }, C _ { 2 }, G _ { \tau _ { k } } \, \langle V _ { f } ( C _ { 2 } ) )$$

$$\leq \ X _ { k - 1 } \,,$$

where Eq. (14) follows by the fact that P τ k ⊆ G τ k +1 , Eq. (15) follows by Eq. (12). Eq. (16) follows by the fact that P τ k was bought and by Eq. (4), and Eq. (41) follows by the fact that x k -1 ∈ C 1 and t k -1 ∈ C 2 .

Therefore, we have that

$$X _ { N } \leq X _ { 1 } - ( N - 1 ) \.$$

Conversely, we have that

$$X _ { N } \ \geq \ \text{dist} ( x _ { N }, t _ { N }, G \, \sum \{ v _ { 1 }, \dots, v _ { N } \} )$$

$$\geq \text{ dist} ( x _ { 1 }, t _ { 1 }, G \, \sum \{ v _ { 1 }, \dots, v _ { N } \} ) - 4$$

$$= \ \text{dist} ( x _ { 1 }, t _ { 1 }, P _ { \tau _ { 1 } } ) - 4 = \text{dist} ( x _ { 1 }, t _ { 1 }, P _ { \tau _ { 1 } } \, \langle \, V _ { f } ( C _ { 2 } ) ) - 4$$

$$\geq \ X _ { 1 } - 4$$

where Eq. (19) follows as G τ N +1 ⊆ G and by Eq. (10), { v , . . . , v 1 N } ⊆ V f ( C 2 ). To see Eq. (20), we need to prove the existence of the intracluster paths R 1 = [ x , z 1 1 , x N ] and R 2 = [ t 1 , z 2 , t N ] in

G \{ v , . . . , v 1 N } where z 1 (resp., z 2 ) is the cluster center of C 1 (resp., C 2 ). By definition, x , x 1 N ∈ C 1 and t 1 , t N ∈ 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 (13), z , z 1 2 / ∈ { v , . . . , v 1 N } .

In addition, by Eq. (12), x , t k k ∈ G \ V f ( C 2 ) for every k ∈ { 1 , . . . , N } and by Eq. (10), it also holds that x , t k k / ∈ { v , . . . , v 1 N } for every k ∈ { 1 , . . . , N } . Hence, R 1 and R 2 exists in G \ { v , . . . , v 1 N } and Eq. (20) follows by the triangle inequality. Eq. (21) follows by Eq. (12) and Eq. (10). Finally, Eq. (22) follows by the fact that P τ 1 was added at step τ 1 , hence P τ 1 ⊆ G τ 2 . We get that N ≤ 5. The claim follows.

By Obs. 2.3(2) and Obs. 2.4, every path P τ k contains at most O n/ ( | ∆ ) = | O n/ S ( | | ) missing edges in G \ G ∆ . Hence,

$$| E ( G _ { \tau ^ { \prime } } \, \langle \, G _ { 0 } ) | \ = \ O ( n / | S | ) \cdot | \mathcal { B } |$$

$$\lq ^ { \prime } _ { \tau ^ { \prime } } \, \sum \, G _ { 0 } ) | \ & = \ \ & O ( n / | S | ) \cdot | \mathcal { B } | \\ & = \ \ & O ( n / | S | ) \cdot \sum _ { C _ { 1 }, C _ { 2 } \in \mathcal { C } } | \mathcal { B } ( C _ { 1 }, C _ { 2 } ) | \\ & \leq \ \ & O ( n / | S | ) \cdot | \mathcal { C } | ^ { 2 } = \widetilde { O } ( ( n / | S | ) ^ { 3 } ) \. \\ & \quad \quad \quad$$

where the last equality follows by the fact that |C| = ˜ O n/ S ( | | ). The claim follows.

## 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 S 4 ( ) 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 4.15 There exists a subgraph H S 8 ( ) ⊆ G with ˜ O (max {| S |· n, ( n/ S | | ) 2 } ) edges s.t. dist( s, t, H 8 ( S ) \ { v } ) ≤ dist( s, t, G \ { v } ) + 8 for every ( s, t ) ∈ S × V and every v ∈ V .

## 4.2.1 Algorithm Cons8SWSpanner for constructing H S 8 ( ) spanner

Step (0-4.1): Same as in Alg. Cons4SWSpanner . Let E local , E far dep be the set of last edges obtained at the end of step (3) and set (4.1) respectively. Let P far 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 P far indep are considered in an arbitrary order. At step τ , we are given G τ ⊆ G and consider the path P τ = P s,t,v . Let D τ = P τ \ π s, t ( ) be the detour segment of P τ (since π s, t ( ) ⊆ T 0 ( S ) is in G 0 , all missing edges of P τ occur on its detour segment).

To decide whether P τ should be added to G τ , the number of pairwise cluster 'distance improvements' is compared to the number of new edges added due to P τ . To do that we compute the set ValSet ( P τ ) containing all pairs of clusters that achieves a better distance if P τ is bought. The value and cost of P τ are computed as follows. Let Val ( P τ ) = | ValSet ( P τ ) | as the number of distance improvements as formally defined later. We next define a key vertex φ τ ∈ V ∆ on the path P τ .

Definition 4.16 Let φ s,t,v (or φ τ for short) be the last vertex on P τ (closest to t ) satisfying that: (N1) LastE ( P τ [ s, φ τ ]) / G ∈ τ , and (N2) v ∈ π near ( s, φ τ ) = π glyph[lscript], ( φ τ ) \ { glyph[lscript] } where glyph[lscript] = LCA ( s, C v ( φ τ )) . If there is no vertex on P τ that satisfies both (N1) and (N2), then let φ τ be the first vertex incident to the first missing edge on P τ \ E G ( τ ) (i.e., such that P τ [ s, φ τ ] is the maximal prefix that is contained in G τ ).

Let Q τ = P τ [ φ , t τ ] and define Cost ( P τ ) = | E Q ( τ ) \ E G ( τ ) | be the number of edges of Q τ that are missing in the current subgraph G τ . Thus Cost ( P τ ) represents the increase in the size of the spanner G τ if the procedure adds Q τ . Our algorithm attempts to buy only the suffix Q τ of P τ when considering P τ . We now define the set ValSet ( P τ ) ⊆ C × C which contains a collection ordered cluster pairs. Let C 1 ( τ ) = C v ( φ τ ) and C 2 ( τ ) = C v ( ) be the clusters of t φ τ and t in G ∆ \ { v } . Let κ = Cost ( P τ ). The candidate P τ is said to be cheap if κ ≤ 4, otherwise it is costly . The definition of ValSet ( P τ ) depends on whether or not the path is cheap. In particular, if P τ is cheap, then let ValSet ( P τ ) = { ( C 1 ( τ ) , C 2 ( τ )) } only if

$$\text{dist} ( \phi _ { \tau }, t, P _ { \tau } ) < \text{dist} ( C _ { 1 } ( \tau ), C _ { 2 } ( \tau ), G _ { \tau } \, \sum V _ { f } ( C _ { 2 } ( \tau ) ) )$$

where V f ( C 2 ( τ )) is as given by Eq. (3), and let ValSet ( P τ ) = ∅ otherwise. Alternatively, if P τ is costly, we do the following.

Definition 4.17 Let U s,t,v = { u 3 +1 glyph[lscript] | glyph[lscript] ∈ { 0 , . . . , glyph[floorleft] ( κ -1) / 3 glyph[floorright]}} ⊆ Q τ be some representative endpoints of missing edges on Q τ satisfying that

$$\text{LastE} ( Q _ { \tau } [ \phi _ { \tau }, u _ { \ell } ] ) \notin G _ { \tau } \text{ for every } u _ { \ell } \in U _ { s, t, v } \text{ and dist} ( u _ { \ell }, u _ { \ell ^ { \prime } }, Q _ { \tau } ) \ \geq \ 3$$

for every u , u glyph[lscript] glyph[lscript] ′ ∈ U s,t,v .

Define

$$\text{valSet} _ { 1 } ( P _ { \tau } ) \ = \ \{ ( C _ { 1 } ( \tau ), C _ { \ell } ) \ | \ C _ { \ell } = C _ { v } ( u _ { \ell } ), u _ { \ell } \in U _ { s, t, v } \\ \text{and dist} ( \phi _ { \tau }, u _ { \ell }, P _ { \tau } ) < \text{dist} ( C _ { 1 } ( \tau ), C _ { \ell }, G _ { \tau } \, \searrow \, V _ { f } ( C _ { \ell } ) ) \}$$

and

$$\text{valSet} _ { 2 } ( P _ { \tau } ) \ = \ \{ ( C _ { \ell }, C _ { 2 } ( \tau ) ) \ | \ C _ { \ell } = C _ { v } ( u _ { \ell } ), u _ { \ell } \in U _ { s, t, v } \\ \text{ and dist} ( u _ { \ell }, t, P _ { \tau } ) < \text{dist} ( C _ { \ell }, C _ { 2 } ( \tau ), G _ { \tau } \, \sum V _ { f } ( C _ { 2 } ( \tau ) ) ) \}$$

Let ValSet ( P τ ) = ValSet 1 ( P τ ) ∪ ValSet 2 ( P τ ). The subpath Q τ is added to G τ resulting in G τ +1 only if

$$\text{Cost} ( P _ { \tau } ) \leq 4 \cdot \text{Val} ( P _ { \tau } )$$

where Val ( P τ ) = | ValSet ( P τ ) . | (Note that when P τ is cheap, Eq. (29) holds iff Eq. (26) holds.) The output of Alg. Cons8SWSpanner is the subgraph H S 8 ( ) = G τ ′ where τ ′ = |P far indep | . This completes the description of the algorithm.

Analysis. Throughout the discussion, a path P s,t,v is a new-ending path, if LastE ( P s,t,v ) / G ∈ 0 (see Eq. (2)). Hence, we consider only P s,t,v ∈ P far indep ( ) paths for clustered vertices t t ∈ V ∆ .

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 π 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 \ { b s,t,v } . Let Q s,t,v = P s,t,v [ φ s,t,v , t ] be the path segment that was considered to be bought in step (4.2) (see Def. 4.16).

## Observation 4.18 Q s,t,v ⊆ D + s,t,v .

Proof: Let x be the first vertex incident to a new-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 φ s,t,v occurs not before x on P s,t,v the observation follows by Lemma 4.4(b).

Lemma 4.19 Let P s,t,v ∈ P far indep ( ) t be a new-ending replacement path. Then for every u k ∈ U s,t,v ∪ { } t with C k = C v ( u k ) it holds that:

- (a) C k = C 1 ( u k ) .
- (b) V ( P s,t i ,v [ b s,t,v , u k ]) ∩ V ( T u , S ( k )) = { b s,t,v , u k } .
- (c) Q s,t,v [ φ s,t,v , u k ] ∩ V f ( C k ) = {∅} .
- (d) v ∈ V f ( C k ) .

Proof: We begin with (a). By the uniqueness of the weight assignment W P , s,t i ,v [ s, u k ] = P s,u k ,v = SP s,u ,G ( k \{ } v , W ). By the uniqueness of the divergence point b s,t,v and in particular by Lemma 4.2(b),

$$b _ { s, t, v } = b _ { s, u _ { k }, v } \.$$

glyph[negationslash]

Since LastE ( P s,u k ,v ) / E ∈ local , concluding that v = z 1 ( u k ) and 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 Def. 4.17), it holds LastE ( P s,u k ,v ) / G ∈ 0 . Since u k ∈ Q s,t,v occurs strictly after φ s,t,v , by the definition Def. 4.16, it holds that u k did not satisfy property (N2). Hence, since LastE ( P s,u k ,v ) / E ∈ local , v / ∈ { z 1 ( u k ) , LCA ( s, C 1 ( u k )) } and hence v ∈ π far ( s, u k ). As LastE ( P s,u k ,v ) / E ∈ far 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 ]) ∩ V ( T u , S ( k )) = { b s,u k ,v , u k } . Hence (b) holds by Eq. (30).

glyph[negationslash]

We now turn to consider claim (c). By Eq. (3), V f ( C v ( u k )) ⊆ T u , S ( k ). Since C v ( u k ) ∩ V f ( C v ( u k )) = ∅ , it holds that u k / V ∈ f ( C v ( u k )), and hence by combining with claim (a), we get that P s,u k ,v [ b s,u k ,v , u k ] ∩ V f ( C v ( u k )) = { b s,u k ,v } . Since by the proof of Lemma 4.4(b), φ s,t,v = b s,u k ,v , hence Q s,t,v [ φ s,t,v , u k ] ∩ V f ( C v ( u k )) = ∅ .

Consider claim (d). By the above, v occurs on the far segment π s, C ( k ) \ { LCA ( s, C k ) } , hence v / C ∈ k . Since ( π s, C ( k ) \ C k ) ⊆ V f ( C k ), (d) holds.

The next observation is useful in our analysis.

Observation 4.20 If φ s,t,v satisfies (N1) and (N2), then there exists a vertex x ∈ C v ( φ s,t,v ) satisfying that v / π s, x ∈ ( ) .

Proof: Let P τ = P s,t,v and φ τ = φ s,t,v . By the uniqueness of the weight assignment W P s,φ , τ [ τ ] = P s,φ τ ,v = SP s,φ ,G ( τ \ { v } , W ). Since φ τ satisfies (N2), it holds that the failing vertex v occurs on π near ( s, φ τ ), strictly below (i.e., closer to φ τ ) the least common ancestor LCA ( s, C v ( φ τ )) on π s, φ ( τ ). Hence, there must exist a vertex x ∈ C v ( φ τ ) such that v / π s, x ∈ ( ) (otherwise, if v is shared by

π s, u ( ) for all cluster members u , then we end with contradiction to the definition of the least common ancestor LCA ( s, C v ( φ τ ))).

We proceed by showing correctness.

Theorem 4.21 H S 8 ( ) is a (8 , S ) FT-spanner.

Proof: Let H = H S 8 ( ). It is required to show that dist( s, t, H \ { v } ) ≤ dist( s, t, G \ { v } ) + 8 for every ( s, t ) ∈ S × V and v ∈ V . By the analysis of Alg. Cons4SWSpanner (Lemma 4.6), it remains to consider the case of independent new-ending paths where P s,t,v ∈ P far indep ( ) for t t ∈ V ∆ .

Let τ be the iteration at which P τ = P s,t,v was considered to be added to the spanner at step (4.2), and let κ = Cost ( P τ ) denote its cost. Let φ τ be as defined in Def. 4.16 and recall that Q τ = P τ [ φ , t τ ] is the candidate suffix to be bought by the procedure. (In particular, Cost ( P τ ) counts the number of edges on Q τ \ E G ( τ ).)

Case (1): Q τ was bought. If φ τ did not satisfy neither properties (N1), (N2) (or both), then P τ [ s, φ τ ] ⊆ G τ . Since P τ = P τ [ s, φ τ ] ◦ Q τ and Q τ was added to the spanner, we get that P τ ⊆ H \{ v } . By Obs.

It remains to consider the complementary case where φ τ satisfies both (N1) and (N2). 4.20, we get that there exist x ∈ C v ( φ τ ) satisfying that v / π s, x ∈ ( ).

Consider the path P = π s, x ( ) ◦ ( x, z v ( φ τ ) , φ τ ). By definition, P ⊆ H \{ } v and by the existence of the intracluster path connecting x and φ τ in G \ { v } , it holds that | P | = dist( s, x, G \ { v } ) + 2 ≤ dist( s, φ τ , G \ { v } ) + 4. Hence, letting P ′ = P ◦ Q τ (where Q τ = P τ [ φ , t τ ]), since Q τ ⊆ H \ { v } , it holds that P ′ ⊆ H \ { v } and | P ′ | ≤ | P τ | +4, as required.

Case (2): Q τ was not bought. Let x ∈ C v ( φ τ ) be defined as follows. If φ τ satisfies both properties (N1) and (N2) of Def. 4.16, then using Obs. 4.20, let x ∈ C v ( φ τ ) be the vertex satisfying that v / π s, x ∈ ( ). Otherwise, if φ τ did not satisfy (N1) or (N2) (or both), let x = φ τ . Note that in any case, it holds that x, φ τ ∈ C v ( φ τ ). We have the following.

## Lemma 4.22 P s,x,v ⊆ H \ { v } .

Proof: If x = φ τ , then it implies that φ τ did not satisfy both of the properties (N1,N2). By Def. 4.16, in such a case φ τ is the vertex incident to the first missing edge on P s,t,v \ E G ( τ ) and hence P s,t,v [ s, x ] = P s,x,v ⊆ G τ \ { v } .

glyph[negationslash]

Otherwise, if x = φ τ , then x ∈ C v ( φ τ ) and by the selection of x , v / π s, x ∈ ( ). Hence, P s,x,v = π s, x ( ) ⊆ H \ { v } .

Recall that C 1 ( τ ) = C v ( φ τ ) and C 2 ( τ ) = C v ( ). t In addition, since v ∈ π far ( s, t ), it holds that v ∈ V f ( C 2 ( τ )).

Case (2.1): P τ is cheap. Since Q τ was not added, Eq. (26) did not hold and hence

$$\text{dist} ( \phi _ { \tau }, t, P _ { \tau } ) \geq \text{dist} ( C _ { 1 } ( \tau ), C _ { 2 } ( \tau ), G _ { \tau } \, \sum V _ { f } ( C _ { 2 } ( \tau ) ) ) \.$$

Let w 1 ∈ C 1 ( τ ) and w 2 ∈ C 2 ( τ ) be a closest pair satisfying that dist( w , w , G 1 2 τ \ V f ( C 2 ( τ ))) = dist( C 1 ( τ ) , C 2 ( τ ) , G τ \ V f ( C 2 ( τ ))). Since the failing vertex v is in V f ( C 2 ( τ )), both auxiliary vertices w 1 and w 2 are in G \{ } v . Consider the following s -t path: P = P 0 ◦ P 1 ◦ P 2 ◦ P 3 where P 0 = P s,x,v , P 1 = [ x, z v ( φ τ ) , w 1 ], P 2 ∈ SP w ,w ,G ( 1 2 τ \ V f ( C 2 ( τ ))), and P 3 = [ w , z 2 v ( ) t , t ]. For an illustration see

Fig. 4. By Lemma 4.22, P 0 ⊆ H \{ } v . Note that since x, w 1 ∈ C v ( φ τ ), the path P 1 exists in H \{ } v . Combining with the definitions of the vertices z v ( x , z ) v ( ) t , w 1 , w 2 , it holds that P ⊆ H \ { v } . So, it remains to bound the length of the path.

$$\text{dist} ( s, t, H \, \{ v \} ) & \ \leq \ \, | P _ { 0 } | + | P _ { 1 } | + | P _ { 2 } | + | P _ { 3 } | \\ & \ = \ \, \text{dist} ( s, x, G \, \{ v \} ) + \text{dist} ( w _ { 1 }, w _ { 2 }, G _ { \tau } \, \| \, V _ { f } ( C _ { 2 } ( \tau ) ) ) + 4 \\ & \ \leq \ \, \text{dist} ( s, \phi _ { \tau }, G \, \| \, \{ v \} ) \\ & \ \, + \ \, \text{dist} ( w _ { 1 }, w _ { 2 }, G _ { \tau } \, \| \, V _ { f } ( C _ { 2 } ( \tau ) ) ) + 6 \\ & \ \leq \ \, \text{dist} ( s, \phi _ { \tau }, G \, \| \, \{ v \} ) + \text{dist} ( \phi _ { \tau }, t, P _ { \tau } ) + 6 \, = | P _ { \tau } | + 6, \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot$$

where Eq. (32) follows by the fact that x, φ τ ∈ C v ( φ τ ) and since G ∆ ⊆ H , it holds that the intracluster path R = [ x, z v ( φ τ ) , φ τ ] exists in G \ { v } , Eq. (33) follows by Eq. (31).

Case (2.2): P τ is costly. Let U s,t,v = { u , . . . , u 1 κ ′ } ⊆ Q τ for κ ′ = glyph[floorleft] κ/ 3 glyph[floorright] ≥ 1 be as defined by Def. 4.17. Since by Obs. 2.3, the diameter of each cluster is 2, each u k ∈ U s,t,v belongs to a distinct cluster C k = C v ( u k ) ∈ C . Hence there are at least κ ′ distinct clusters on Q τ .

Acluster C k = C v ( u k ) is a contributor if adding Q τ to G τ improves either the C 1 ( τ ) -C k distance (i.e., ( C 1 ( τ ) , C k ) ∈ ValSet 1 ( P τ )) or the C 2 ( τ ) -C k distance (i.e., ( C , C k 2 ( τ )) ∈ ValSet 2 ( P τ )) 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 κ ′ clusters contribute to Val ( P τ ) (either with C 1 ( τ ) or with C 2 ( τ ) or both). It then holds that Val ( P τ ) ≥ κ ′ ≥ Cost ( P τ ) / 4. Hence, by Eq. (29), we get a contradiction to the fact that the suffix Q τ was not added to G τ .

In the other case, there exists at least one neutral cluster C glyph[lscript] such that

$$\text{dist} ( C _ { 1 } ( \tau ), C _ { k }, \widehat { H } _ { 1 } ) \ & \leq \ \text{dist} ( \phi _ { \tau }, u _ { k }, P _ { \tau } ) \ \text{ and } \\ \text{dist} ( C _ { k }, C _ { 2 } ( \tau ), \widehat { H } _ { 2 } ) \ & \leq \ \text{dist} ( u _ { k }, t, P _ { \tau } )$$

where ̂ H 1 = G τ \ V f ( C k ) and ̂ H 2 = G τ \ V f ( C 2 ( τ )). Let w 1 ∈ C 1 ( τ ) and w 2 ∈ C k be the pair of vertices satisfying dist( w , w , H 1 2 ̂ 1 ) = dist( C 1 ( τ ) , C k , H ̂ 1 ). In addition, let y 1 ∈ C k and y 2 ∈ C 2 ( τ ) be the pair satisfying dist( y , y 1 2 , H ̂ 2 ) = dist( C , C k 2 ( τ ) , H ̂ 2 ).

Let Q 1 = [ x, z v ( φ τ ) , w 1 ], Q 2 = [ w , z 2 v ( u k ) , y 1 ] and Q 3 = [ y , z 2 v ( ) t , t ] be the intracluster paths in C 1 ( τ ) , C k and C 2 ( τ ) respectively. Note that by definition x, w 1 ∈ C v ( φ τ ).

Since by Lemma 4.19(c), v ∈ V f ( C k ) ∩ V f ( C 2 ( τ )), it also holds that Q , Q , Q 1 2 3 ⊆ H \ { v } . Let P ′ = P 0 ◦ Q 1 ◦ P 1 ◦ Q 2 ◦ P 2 ◦ Q 3 where P 0 = P s,x,v , P 1 ∈ SP w ,w ,H ( 1 2 ̂ 1 ) and P 2 ∈ SP y ,y , H ( 1 2 ̂ 2 ). By Lemma 4.22, P 0 ⊆ H \ { v } and by the above explanation, P ′ ⊆ H \ { v } . So, it remains to bound the length of the s -t path P ′ .

$$\text{bound the length of the $s-t$ path $P$}. \\ \text{dist} ( s, t, H \, \{ v \} ) \, & \, \leq \, & | P ^ { \prime } | = | P _ { 0 } | + | P _ { 1 } | + | P _ { 2 } | + 6 \\ & \, = \, & \text{dist} ( s, x, G \, \{ v \} ) + \text{dist} ( w _ { 1 }, w _ { 2 }, \widehat { H } _ { 1 } ) + \text{dist} ( y _ { 1 }, y _ { 2 }, \widehat { H } _ { 2 } ) + 6 \\ & \, \leq \, & \text{dist} ( s, \phi _ { \tau }, G \, \{ v \} ) + \text{dist} ( w _ { 1 }, w _ { 2 }, \widehat { H } _ { 1 } ) + \text{dist} ( y _ { 1 }, y _ { 2 }, \widehat { H } _ { 2 } ) + 8 \\ & \, = \, & \text{dist} ( s, \phi _ { \tau }, G \, \{ v \} ) + \text{dist} ( C _ { 1 } ( \tau ), C _ { k }, \widehat { H } _ { 1 } ) \\ & \, + \, & \text{dist} ( C _ { k }, C _ { 2 } ( \tau ), \widehat { H } _ { 2 } ) + 8 \\ & \, \leq \, & \text{dist} ( s, \phi _ { \tau }, G \, \{ v \} ) + \text{dist} ( \phi _ { \tau }, u _ { k }, P _ { \tau } ) + \text{dist} ( u _ { k }, t, P _ { \tau } ) + 8 \\ & \, = \, & | P _ { s, t, v } | + 8 \, \\ & \, \quad \quad \quad$$

where the first inequality follows by the fact that x, φ τ ∈ C v ( φ τ ) and hence the intraclusrer path R = [ x, z v [ φ τ ] , φ τ ] exists in G \ { v } and last inequality follows Eq. (34). The claim follows.

8-additive sourcewise  FT-spanner.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0409v1-figure-48f3adb2-8ce5-4191-b861-493b3be163a3.jpg)

Figure 4: Schematic illustration of the path-buying procedure of Alg. Cons8SWSpanner . The horizontal path is P τ = P s,t,v whose segment Q s,t,v = P s,t,v [ φ s,t,v , t ] was considered to be bought at time τ . The green paths correspond to the shortest paths in T 0 ( s ). Red edges correspond to missing edges on P s,t,v \ E G ( τ ). The vertex φ s,t,v satisfies properties (N1) and (N2), hence it is incident to a missing edge and the failing vertex v occurs on π s, φ ( s,t,v ) strictly below the LCA vertex LCA ( φ s,t,v ) = LCA ( s, C v ( φ s,t,v )). The vertex x ∈ C v ( φ s,t,v ) satisfies that v / π s, x ∈ ( ). The s -t replacement path in H \ { v } is given by traveling from s to x on π s, x ( ) and then use the closest vertex pairs w , w 1 2 and y , y 1 2 .

Finally, we turn to bound the size of H S 8 ( ) and claim the following.

$$\text{Lemma } 4. 2 3 \ | E ( H _ { 8 } ( S ) ) | = \widetilde { O } ( \max \{ | S | \cdot n, n ^ { 2 } / | S | ^ { 2 } \} ).$$

Proof: Let H = H S 8 ( ). 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 B ⊆ P far indep be the set of paths corresponding to the paths segments that were bought in the path-buying phase. For every ordered pair of clusters, C , C 1 2 ∈ C let B ( C , C 1 2 ) = { P τ ∈ B | ( C , C 1 2 ) ∈ ValSet ( P τ ) } .

Clearly, B = ⋃ C ,C 1 2 ∈C B ( C , C 1 2 ). We next claim that since the diameter of each cluster is small, it holds that the cardinality of each subset B ( C , C 1 2 ) is small as well.

Lemma 4.24 |B ( C , C 1 2 ) | ≤ 5 for every C , C 1 2 ∈ C .

Proof: Fix C , C 1 2 ∈ C and let B ( C , C 1 2 ) = { P τ 1 , . . . , P τ N } be sorted according to the time τ k their segment Q τ was added to the spanner, for every k ∈ { 1 , . . . , N } where N = |B ( C , C 1 2 ) . | Let P τ k = P s k ,t k ,v k . Let p , q k k ∈ P τ k be 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 .

glyph[negationslash]

Recall that φ τ k is the first vertex of Q τ k (see Def. 4.16). Let C glyph[lscript] = C v k ( u glyph[lscript] ) be the cluster of u glyph[lscript] for every u glyph[lscript] ∈ U s k ,t k ,v k (see Def. 4.17). By Obs. 2.3, it holds that C glyph[lscript] = C glyph[lscript] ′ for every u , u glyph[lscript] glyph[lscript] ′ ∈ U s k ,t k ,v k . Recall that for every u glyph[lscript] ∈ U s k ,t k ,v k , P s,u ,v glyph[lscript] = P s,t,v [ s, u glyph[lscript] ]. Since LastE ( P s,u ,v glyph[lscript] ) / E ∈ local , it holds that v / ∈ { z 1 ( u glyph[lscript] ) , LCA ( s, C 1 ( u glyph[lscript] )) } . Combining that with the fact that u glyph[lscript] ∈ U s k ,t k ,v k did not satisfy property (N2) (see Def. 4.16 and Def. 4.17), we conclude that v k ∈ π far ( s k , u glyph[lscript] ). Since q k ∈ U s k ,t k ,v k ∪ { t k } , using Lemma 4.19(c), it holds that

$$v _ { k } \in V _ { f } ( C _ { 2 } ) \text{ for every } k \in \{ 1, \dots, N \}$$

and by Lemma 4.19(b),

$$P _ { \tau _ { k } } [ p _ { k }, q _ { k } ] \subseteq Q _ { \tau _ { k } } [ p _ { k }, q _ { k } ] \subseteq G \, \sum V _ { f } ( C _ { 2 } ) \.$$

Since C 1 = C v k ( p k ) and C 2 = C v k ( q k ), for every k ∈ { 1 , . . . , N } , it holds that z v 1 ( p 1 ) = ... = z v N ( p N ) and also z v 1 ( q 1 ) = ... = 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

$$z _ { 1 }, z _ { 2 } & \notin \{ v _ { 1 }, \dots, v _ { N } \}.$$

Denote

$$X _ { k } = \text{dist} ( p _ { k }, q _ { k }, G _ { \tau _ { k + 1 } } \, \langle V _ { f } ( C _ { 2 } ) ).$$

We now show that X &lt; X k k -1 for every k ∈ { 2 , . . . N } .

Each time a path segment Q τ k is purchased at time τ k , it implies that

$$X _ { k } \ \leq \ \text{dist} ( p _ { k }, q _ { k }, P _ { \tau _ { k } } \, \langle V _ { f } ( C _ { 2 } ) )$$

$$= \text{ dist} ( p _ { k }, q _ { k }, P _ { \tau _ { k } } )$$

$$< \text{ dist} ( C _ { 1 }, C _ { 2 }, G _ { \tau _ { k } } \, \langle V _ { f } ( C _ { 2 } ) )$$

$$\leq \ X _ { k - 1 }$$

where Eq. (38) follows by the fact that P τ k [ p , q k k ] ⊆ Q τ k ⊆ G τ k +1 , Eq. (39) follows by Eq. (36), Eq. (40) follows by the fact that Q τ k was bought and by Eqs. (27) and (28), and Eq. (41) follows by the fact that p k -1 ∈ C 1 and q k -1 ∈ C 2 .

Therefore, we have that

$$X _ { N } \leq X _ { 1 } - ( N - 1 ) \.$$

Conversely, we have that

$$X _ { N } \ \geq \ \text{dist} ( p _ { N }, q _ { N }, G \, \langle \, \{ v _ { 1 }, \dots, v _ { N } \} )$$

$$\geq \ \text{dist} ( p _ { 1 }, q _ { 1 }, G \, \sum \{ v _ { 1 }, \dots, v _ { N } \} ) - 4$$

$$= \ \text{dist} ( p _ { 1 }, q _ { 1 }, P _ { \tau _ { 1 } } ) - 4 = \text{dist} ( p _ { 1 }, q _ { 1 }, P _ { \tau _ { 1 } } \ \| \ V _ { f } ( C _ { 2 } ) ) - 4$$

$$\geq \ X _ { 1 } - 4$$

where Eq. (43) follows as G τ N +1 ⊆ G and by Eq. (35), { v , . . . , v 1 N } ⊆ V f ( C 2 ). To see Eq. (44), note that p , p 1 N ∈ C 1 and q , q 1 N ∈ C 2 and by Obs. 2.3(3) the diameter of the cluster is 2. It remains to show that the intracluster paths R 1 = [ p , z 1 1 , p N ] , R 2 = [ q , z 1 2 , q N ] exist in the surviving graph G \ { v , . . . , v 1 N } . This holds since by Eq. (37), z , z 1 2 / ∈ { v , . . . , v 1 N } , and by Eq. (35) and (36). Eq. (45) follows by Eq. (36). Finally, Eq. (46) follows by the fact that P τ 1 [ p , q 1 1 ] ⊆ Q τ 1 was added at step τ 1 , hence P τ 1 [ p , q 1 1 ] ⊆ G τ 2 . By combining with Eq. (42), we get that N ≤ 5. The claim follows.

Finally, since for every path P ∈ B , it holds that Cost ( P ) ≤ 4 · Val ( P ), we get that

$$| E ( G _ { \tau ^ { \prime } } ) \, \sum \, E ( G _ { 0 } ) | \ & = \ \sum _ { P \in \mathcal { B } } \cosh ( P ) \leq 4 \sum _ { P \in \mathcal { B } } \text{vat} ( P ) \leq 4 \sum _ { C _ { 1 }, C _ { 2 } \in \mathcal { C } } | \mathcal { B } ( C _ { 1 }, C _ { 2 } ) | \\ & \leq \ O ( | \mathcal { C } | ^ { 2 } ) = \widetilde { O } ( ( n / | S | ) ^ { 2 } ) \.$$

where the last equality follows by the fact that there are |C| = | Z | = ˜ O n/ S ( | | ) clusters. The claim follows.

Additive stretch 6 (for all pairs). Thm. 1.2 follows immediately by Lemma 4.1. This should be compared with the single source additive FT-spanner H 4 ( { } s ) of [18] and the (all-pairs, non FT) 6-additive spanner, both with ˜ O n ( 4 3 / ) edges.

## References

- [1] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. , 28(4):1167-1181, 1999.
- [2] Mathias Bæk Tejs Knudsen. Additive Spanners: A Simple Construction. In SWAT , 277-281, 2014.
- [3] S. Baswana and S. Sen. Approximate distance oracles for unweighted graphs in expected O n ( 2 ) time. ACM Trans. Algorithms , 2(4):557-577, 2006.
- [4] S. Baswana and N. Khanna. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graph. In STACS , 513-524, 2010.
- [5] S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. Additive spanners and ( α, β )-spanners. ACM Trans. Algo. 7, A.5, 2010.
- [6] A. Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms , 2010.
- [7] A. Bernstein and D. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proc. 41st ACM Symp. on Theory of Computing , 101-110, 2009.
- [8] G. Braunschvig, S. Chechik and D. Peleg. Fault tolerant additive spanners. In WG , 206-214, 2012.
- [9] S. Chechik, M. Langberg, D. Peleg, and L. Roditty. f -sensitivity distance oracles and routing schemes. Algorithmica 63 , (2012), 861-882.
- [10] S. Chechik, M. Langberg, D. Peleg, and L. Roditty. Fault-tolerant spanners for general graphs. In STOC , 435-444, 2009.
- [11] S. Chechik. New Additive Spanners. In SODA , 2013.
- [12] M. Cygan, F. Grandoni and T. Kavitha. On Pairwise Spanners. In STACS , 209-220, 2013.
- [13] M. Dinitz and R. Krauthgamer. Fault-tolerant spanners: better and simpler. In PODC , 2011, 169-178.
- [14] D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM J. Computing , 29(5):17401759, 2000.
- [15] M. Elkin and D. Peleg. (1 + ε, β )-Spanner Constructions for General Graphs. SIAM Journal on Computing , 33(3): 608-631, 2004.
- [16] F. Grandoni and V.V Williams. Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. In FOCS , 2012.

- [17] M. Parter and D. Peleg. Sparse Fault-tolerant BFS trees. In ESA , 2013.
- [18] M. Parter and D. Peleg. Fault Tolerant Approximate BFS Structures. In SODA , 2014.
- [19] L. Roditty and U. Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms ,2012.
- [20] M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In SODA , 802-809, 2006.
- [21] O. Weimann and R. Yuster. Replacement paths via fast matrix multiplication. FOCS , 2010.
- [22] D.P Woodruff. Lower bounds for additive spanners, emulators, and more. In FOCS , 389-398, 2006.
- [23] D.P Woodruff. Additive spanners in nearly quadratic time. In ICALP , 463-474, 2010.
Merav Parter
Vertex Fault Tolerant Additive Spanners
A {\em 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 {\em 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 \emph{additive} spanner for (the surviving part of) $G$, satisfying
$dist(s,t,H\setminus \{v\}) \leq 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$ \emph{edges} has been considered
by Braunschvig et. al. The problem of handling \emph{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 $\widetilde{O}(n^{5/3})$
edges. Our second result is an FT-spanner with additive stretch $6$ and
$\widetilde{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 adopted to failure prone settings. Finally, we
also describe two constructions for {\em 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).