Effective Edge-Fault-Tolerant Single-Source
Spanners via Best (or Good) Swap Edges
Davide Bilò1 , Feliciano Colella2 , Luciano Gualà3 , Stefano Leucci4 , and
Guido Proietti5,6

arXiv:1707.08861v1 [] 27 Jul 2017

1

Dipartimento di Scienze Umanistiche e Sociali, University of Sassari, Italy
davide.bilo@uniss.it
2
Gran Sasso Science Institute, L’Aquila, Italy. feliciano.colella@gssi.it
3
Dipartimento di Ingegneria dell’Impresa, University of Rome “Tor Vergata”, Italy.
guala@mat.uniroma2.it
4
Department of Computer Science, ETH Zürich, Switzerland.
stefano.leucci@inf.ethz.ch
5
Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, University of
L’Aquila, Italy. guido.proietti@univaq.it
6
Istituto di Analisi dei Sistemi ed Informatica, CNR, Rome, Italy.

Abstract. Computing all best swap edges (ABSE) of a spanning tree T
of a given n-vertex and m-edge undirected and weighted graph G means
to select, for each edge e of T , a corresponding non-tree edge f , in such a
way that the tree obtained by replacing e with f enjoys some optimality
criterion (which is naturally defined according to some objective function
originally addressed by T ). Solving efficiently an ABSE problem is by
now a classic algorithmic issue, since it conveys a very successful way
of coping with a (transient) edge failure in tree-based communication
networks: just replace the failing edge with its respective swap edge, so
as that the connectivity is promptly reestablished by minimizing the
rerouting and set-up costs. In this paper, we solve the ABSE problem
for the case in which T is a single-source shortest-path tree of G, and
our two selected swap criteria aim to minimize either the maximum or
the average stretch in the swap tree of all the paths emanating from
the source. Having these criteria in mind, the obtained structures can
then be reviewed as edge-fault-tolerant single-source spanners. For them,
we propose two efficient algorithms running in O(mn + n2 log n) and
O(mn log α(m, n)) time, respectively, and we show that the guaranteed
(either maximum or average, respectively) stretch factor is equal to 3,
and this is tight. Moreover, for the maximum stretch, we also propose an
almost linear O(m log α(m, n)) time algorithm computing a set of good
swap edges, each of which will guarantee a relative approximation factor
on the maximum stretch of 3/2 (tight) as opposed to that provided by
the corresponding BSE. Surprisingly, no previous results were known for
these two very natural swap problems.

2

1

Davide Bilò et al.

Introduction

Nowadays there is an increasing demand for an efficient and resilient information
exchange in communication networks. This means to design on one hand a
logical structure onto a given communication infrastructure, which optimizes
some sought routing protocol in the absence of failures, and on the other hand,
to make such a structure resistant against possible link/node malfunctioning, by
suitably adding to it a set of redundant links, which will enter into operation as
soon as a failure takes place.
More formally, the depicted situation can be modeled as follows: the underlying communication network is an n-vertex and m-edge undirected input
graph G = (V (G), E(G), w), with positive real edge weights defined by w, the
logical (or primary) structure is a (spanning) subgraph H of G, and finally the
additional links is a set of edges A in E(G) \ E(H). Under normal circumstances,
communication takes place on H, by following a certain protocol, but as soon
as an edge in H fails, then one or more edges in A come into play, and the
communication protocol is suitably adjusted.
In particular, if the primary structure is a (spanning) tree of G, then a very
effective way of defining the set of additional edges is the following: with each tree
edge, say e, we associate a so-called best swap edge, namely a non-tree edge that
will replace e once it (transiently) fails, in such a way that the resulting swap tree
enjoys some nice property in terms of the currently implemented communication
protocol. By doing in this way, rerouting and set-up costs will be minimized, in
general, and the quality of the post-failure service remains guaranteed. Then, an
all best swap edges (ABSE) problem is that of finding efficiently (in term of time
complexity) a best swap edge for each tree edge.
Due to their fault-tolerance application counterpart, ABSE problems received
a large attention by the algorithmic community. In such a framework, a key role
has been played by the Shortest-Path Tree (SPT) structure, which is commonly
used for implementing efficiently the broadcasting communication primitive.
Indeed, it is was shown already in [15] that an effective post-swap broadcast
protocol can be put in place just after the original SPT undergoes an edge failure.
Not surprisingly then, several ABSE problems w.r.t. an SPT have been studied
in the literature, for many different swap criteria.
Previous work on swapping in an SPT. Since an SPT enjoys several optimality criteria when looking at distances from the source, say s, several papers
have analyzed the problem in various respects. However, most of the efforts
focused on the minimization w.r.t. the following two swap criterion: the maximum/average distance from s to any node which remained disconnected from
s after a failure. The currently fastest solutions for these two ABSE problems
run in O(m log α(m, n)) time [5] and O(m α(n, n) log2 n) time [8], respectively.
Moreover, it has been shown that in the swap tree the maximum (resp., average)
distance of the disconnected nodes from s is at most twice (resp., triple) that of
the new optimum SPT [18], and these bounds are tight.

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

3

Other interesting swap criteria which have been analyzed include the minimization of the maximum increase (before and after the failure) of the distance
from s, and the minimization of the distance from s to the root of the subtree
that gets disconnected after the failure [17]. Besides the centralized setting, all
these swap problems have been studied also in a distributed framework (e.g., see
[10,11,12,7]).
On the other hand, no results are known for the case in which one is willing
to select a BSE with the goal of minimizing either the maximum or the average
stretch from the source s of the disconnected nodes, where the stretch of a node
is measured as the ratio between its distance from s in the swap tree and in a
new optimum SPT. This is very surprising, since they are (especially the former
one) the universally accepted criterion leading to the design of a spanner, i.e., a
sparse subgraph preserving shortest paths (between pairs of vertices of interest)
in a graph (also in the presence of failures).
In this paper, we aim to fill this gap, by providing efficient solutions exactly
for these two swap criteria.
Our results. Let us denote by ABSE-MS and ABSE-AS the ABSE problem w.r.t.
the maximum and the average stretch swap criterion, respectively. For such
problems, we devise two efficient algorithms running in O(mn + n2 log n) and
O(mn log α(m, n)) time, respectively. Notice that both solutions incorporate
the running time for computing all the replacement shortest paths from the
source after the failure of every edge of the SPT, as provided in [13], whose
computation essentially dominates in an asymptotic sense the time complexity.
Our two solutions are based on independent ideas, as described in the following:
– for the ABSE-MS problem, we develop a centroid decomposition of the SPT,
and we exploit a distance property that has to be enjoyed by a BSE w.r.t.
a nested and log-depth hierarchy of centroids, which will be defined by the
subtree detached from the source after the currently analyzed edge failure.
A further simple filtering trick on the set of potential swap edges will allow
to reduce them from O(m) to O(n), thus returning the promised O(n2 log n)
time.
– for the ABSE-AS problem, we instead suitably combine a set of linearlycomputable (at every edge fault) information, that essentially will allow to
describe in O(1) time the quality of a swap edge. This procedure is in principle
not obvious, since to compute the average stretch we need to know, for each
swap edge, the O(n) distances to all the nodes in the detached subtree. Again,
by filtering on the set of potential swap edges, we will get an O(n2 ) running
time, which will be absorbed by the all-replacement paths time complexity.
Concerning the quality of the corresponding swap trees, we instead show that
the guaranteed (either maximum or average, respectively) stretch factor w.r.t.
the paths emanating from the source (in the surviving graph) is equal to 3,
and this is tight. By using a different terminology, our structures can then be
revised as edge-fault-tolerant single-source 3-spanners, and we qualified them as

4

Davide Bilò et al.

effective since they can be computed quickly, are very sparse, provide a very
simple alternative post-failure routing, and finally have a small (either maximum
or average) stretch.
Although the proposed solutions are quite efficient, their running time can
become prohibitive for large and dense input graphs, since in this case they would
amount to a time cubic in the number of vertices. Unfortunately, it turns out that
their improvement is unlikely to be achieved, unless one could avoid the explicit
recomputation of all post-failure distances from the source. To circumvent this
problem, we then adopt a different approach, which by the way finds application
for the (most relevant) max-stretch measure only: we renounce to optimality in
the detection of a BSE, in return of a substantial improvement (in the order
of a linear factor in n) in the runtime. More precisely, for such a measure, we
will compute in an almost linear O(m log α(m, n)) time a set of good swap edges
(GSE), each of which will guarantee a relative approximation factor on the
maximum stretch of 3/2 (tight) as opposed to that provided by the corresponding
BSE. Moreover, a GSE will still guarantee an absolute maximum stretch factor
w.r.t. the paths emanating from the source (in the surviving graph) equal to 3
(tight).
Besides that, we also point out another important feature concerned with the
computation in a distributed setting of all our good swap edges. Indeed, in [7]
it was shown that they can be computed in an asynchronous message passing
system in essentially optimal ideal time,7 space usage, and message complexity,
as opposed to the recomputation of all the corresponding BSE, for which no
efficient solution is currently available.
Other related results. Besides swap-based approaches, an SPT can be made
edge-fault-tolerant by further enriching the set of additional edges, so that the
obtained structure has almost-shortest paths emanating from the source, once an
edge fails. The currently best trade off between the size of the set of additional
edges and the quality of the resulting paths emanating from s is provided in
[3], where the authors showed that for any arbitrary constant ε > 0, one can
compute in polynomial time a slightly superlinear (in n, and depending on ε)
number of additional edges in such a way that the resulting structure retains
(1 + ε)-stretched post-failure paths from the source.
For the sake of completeness, we also quickly recall the main results concerned
with ABSE problems. For the minimum spanning tree (MST), a BSE is of course
one minimizing the cost of the swap tree, i.e., a swap edge of minimum cost. This
problem is also known as the MST sensitivity analysis problem, and can be solved
in O(m log α(m, n)) time [19]. Concerning the minimum diameter spanning tree,
a BSE is instead one minimizing the diameter of the swap tree [14,17], and
the best solution runs in O(m log α(m, n)) time [5]. Regarding the minimum
routing-cost spanning tree, a BSE is clearly one minimizing the all-to-all routing
7

This is the time obtained with the ideal assumption that the communication time of
each message to a neighboring process takes constant time, as in the synchronous
model.

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

5

cost of the swap tree [21], and the fastest
 solutions for solving this problem has a
running time of O m2O(α(n,n)) log2 n [4]. Finally, for a tree spanner, a BSE is
one minimizing the maximum stretch w.r.t. the all pair distances, and the fastest
solution to date run in O(m2 log α(m, n)) time [1].
To conclude, we point out that the general problem of designing fault-tolerant
spanners for the all-to-all case has been extensively studied in the literature, and
we refer the interested reader to [6,9,2] and the references therein.

2

Problem Definition

Let G = (V (G), E(G), w) be a 2-edge-connected, edge-weighted, and undirected
graph with cost function w : E(G) → R+ . We denote by n and m the number
of vertices and edges of G, respectively. If X ⊆ V , let E(X) be the set of edges
incident to at least one vertex in X. Given an edge e ∈ E(G), we will denote by
G − e the graph obtained from G by removing edge e. Similarly, given a vertex
v ∈ V (G), we will denote by G − v the graph obtained from G by removing
vertex v and all its incident edges. Let T be an SPT of G rooted at s ∈ V (G).
Given an edge e ∈ E(T ), we let C(e) be the set of all the swap edges for e, i.e., all
edges in E(G) \ {e} whose endpoints lie in two different connected components
of T − e, and let C(e, X) be the set of all the swap edge for e incident to a vertex
in X ⊆ V (G). For any e ∈ E(T ) and f ∈ C(e), let Te/f denote the swap tree
obtained from T by replacing e with f . Let Tv = (V (Tv ), E(Tv )) be the subtree
of T rooted at v ∈ V (G). Given a pair of vertices u, v ∈ V (G), we denote by
dG (u, v) the distance between u and v in G. Moreover, for a swap edge f = (x, y),
we assume that the first appearing endvertex is the one closest to the source,
and we may denote by w(x, y) its weight. We define the stretch factor of y w.r.t.
T (s,y)
s, T, G as σG (T, y) = ddG
(s,y) .
Given an SPT T of G, the ABSE-MS problem is that of finding, for each edge
e = (a, b) ∈ E(T ), a swap edge f ∗ such that:



f ∗ ∈ arg min µ(f ) := max σG−e Te/f , v .
f ∈C(e)

v∈V (Tb )

Similarly, the ABSE-AS problem is that of finding, for each edge e = (a, b) ∈ E(T ),
a swap edge f ∗ such that:
(
)
X

1
f ∗ ∈ arg min λ(f ) :=
σG−e Te/f , v .
|V (Tb )|
f ∈C(e)
v∈V (Tb )

We will call µ(f ) (resp., λ(f )) the max-(resp., avg-)stretch of f w.r.t. e.

3

An Algorithm for ABSE-MS

In this section we will show an efficient algorithm to solve the ABSE-MS problem in
O(mn + n2 log n) time. Notice that a brute-force approach would require O(mn2 )

6

Davide Bilò et al.

time, given by the O(n) time which is needed to evaluate the quality of each of
the O(m) swap edges, for each of the n − 1 edges of T . Our algorithm will run
through n − 1 phases, each returning in O(m + n log n) time a BSE for a failing
edge of T , as described in the following.
Let us fix e = (a, b) as the failing edge. First, we compute in O(m + n log n)
time all the distances in G − e from s. Then, we filter the O(m) potential swap
edges to O(n), i.e., at most one for each node v in Tb . Such a filtering is simply
obtained by selecting, out of all edges f = (x, v) ∈ C(e, {v}), the one minimizing
the measure dG (s, x) + w(f ). Indeed, it is easy to see that the max-stretch of
such selected swap edge is never worse than that of every other swap edge in
C(e). This filtering phase will cost O(m) total time. As a consequence, we will
henceforth assume that |C(e)| = O(n).
Then, out of the obtained O(n) swap edges for e, we further restrict our
attention to a subset of O(log n) candidates as BSE, which are computed as
follows. Let Λ denote a generic subtree of Tb , and assume that initially Λ = Tb .
First of all, we compute in O(|V (Λ)|) time a centroid c of Λ, namely a node
whose removal from Λ splits Λ in a forest F of subtrees, each having at most
|V (Λ)|/2 nodes [16]; then, out of all the swap edges, we select a candidate edge
f minimizing the distance from s to c in Te/f , i.e.,

f ∈ arg 0 min
dT (s, x0 ) + w(x0 , v 0 ) + dT (v 0 , c) ;
0
(x ,v )∈C(e)

then, we compute a critical node z for the selected swap edge f , i.e.,

z ∈ arg 0 max σG−e Te/f , z 0 .
z ∈V (Tb )

We now select a suitable subtree Λ0 of the forest F , and we pass to the selection
of the next candidate BSE by recursing on Λ0 , until |V (Λ0 )| = 1. More precisely,
Λ0 is the first tree of F containing the first vertex of V (Λ) that is encountered
by following the path in T from z towards c (see Figure 1).
Due to the
 property of the centroid, the number of recursions will be
O log |V (Tb )| = O(log n), as promised, each costing O(n) time. Moreover,
at least one of the candidate edges will be a BSE for e, and hence it suffices
to choose the edge minimizing the maximum stretch among the corresponding
O(log n) candidate edges. This step is done within the recursive procedure by
comparing the current candidate edge f with the best candidate resulting from
the nested recursive calls.
A more formal description of each phase is shown in Algorithm 1. In the
following we prove the correctness of our algorithm.
Lemma 1. Let e = (a, b) be a failing edge,and let Λ be a subtree of Tb . Given a
vertex c ∈ V (Λ), let f ∈ arg min(x0 ,v0 )∈C(e) dT (s, v 0 ) + w(x0 , v 0 ) + dT (v 0 , c) and
let z be a critical node for f . Let F be the forest obtained by removing the edges
incident to c from Λ, and let Λ0 be the tree of F containing the first vertex of the
path from z to c in T that is also in V (Λ). For any swap edge f 0 ∈ C(e, V (Λ)),
if µ(f 0 ) < µ(f ) then f 0 ∈ C(e, V (Λ0 )).

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

7

s
x0

x

a
e

C(e)
f0

b

f
v

v0

c

Λ

Λ0
z

Fig. 1. The situation illustrated in Lemma 1. The subtree Λ is represented by the three
gray triangles along with the vertex c. f = (x, v) is the candidate swap edge for e
that minimizes dT (s, x) + w(f ) + dT (v, c), and z is its corresponding critical node. The
algorithm will compute the next candidate swap edge by recursing on Λ0 .

Proof. Let f = (x, v) and f 0 = (x0 , v 0 ). We show that if v 0 ∈ V (Λ) \ V (Λ0 ) then
µ(f 0 ) ≥ µ(f ) (see also Figure 1). Indeed:
 dTe/f 0 (s, z)
dT (s, x0 ) + w(f 0 ) + dT (v 0 , c) + dT (c, z)
µ(f 0 ) ≥ σG−e Te/f 0 , z =
=
dG−e (s, z)
dG−e (s, z)

d
(s,
z)
dT (s, x) + w(f ) + dT (v, c) + dT (c, z)
T /f
≥
≥ e
= σG−e Te/f , z
dG−e (s, z)
dG−e (s, z)
= µ(f ),
where we used the equality dT (v 0 , z) = dT (v 0 , c) + dT (c, z), which follows from
the fact that the path from v 0 to z in T must traverse c as v 0 and z are in two
different trees of F .
t
u

Lemma 2. If C e, V (Λ) contains a BSE for e then ABSE-MS(e, Λ) returns a
BSE for e.
Proof. First of all notice that Algorithm 1 only returns edges in C(e).

We prove the claim by induction on |V (Λ)|. If |V (Λ)| = 1 and C e, V (Λ)
contains a BSE f ∗ for e, then let f be the edge of C(e) returned by Algorithm 1
and let V (Λ) = {c}. By choice of f , for every v ∈ V (Tb ),
dTe/f (s, v) ≤ dTe/f (s, c) + dT (c, v) = dTe/f ∗ (s, c) + dT (c, v) = dTe/f ∗ (s, v),
from which we derive that µ(f ) = µ(f ∗ ), and the claim follows.
If |V (Λ)| > 1 and C e, V (Λ) contains a BSE for e, we distinguish two cases
depending on whether the edge f computed by Algorithm 1 is a BSE for e

8

Davide Bilò et al.

Algorithm 1: ABSE-MS(e, Λ)
Input : a failing edge e = (a, b) ∈ E(T ), a subtree Λ of Tb .
Output : an edge f ∈ C(e). If C e, V (Λ) contains a BSE for e, f is a BSE for e.
1
2

c ← Centroid of Λ;
Let f ∈ arg 0 min
0

(x ,v )∈C(e)

3



dT (s, x0 ) + w(x0 , v 0 ) + dT (v 0 , c) ;

if |V (Λ)| = 1 then return f ;

8


Let z ∈ arg maxz0 ∈V (Tb ) σG−e Te/f , z 0 ;
Let F be the forest obtained by removing the edges incident to c from Λ;
y ← first vertex along the path from z towards c in T that is also in V (Λ);
Λ0 ← tree of F containing y;
f 0 ← ABSE-MS(e, Λ0 );

9

if µ(f 0 ) < µ(f ) then return f 0 else return f ;

4
5
6
7

or not. If that is the case, then µ(f ) ≤ µ(f 00 ) ∀f 00 ∈ C(e) and the algorithm
0
correctly returns f . Otherwise, by Lemma
 1, any edge f ∈0 C(e, V (Λ)) such that
0
0
µ(f ) < µ(f ) must belong to C e, V (Λ ) . It follows that Λ contains a BSE for e
and since 1 ≤ |V (Λ0 )| < |V (Λ)| we have, by inductive hypothesis, that the edge
f 0 returned by ABSE-MS(G, e, Λ0 ) is a BSE for e. Clearly µ(f 0 ) < µ(f ) and hence
Algorithm 1 correctly returns f 0 .
t
u
Since each invocation of Algorithm 1 requires O(n) time, Lemma 2 together
with the previous discussions allows us to state the main theorem of this section:
Theorem 1. There exists an algorithm that solves the ABSE-MS problem in
O(mn + n2 log n) time.

4

An Algorithm for ABSE-AS

In this section we show how the ABSE-AS problem can be solved efficiently in
O(mn log α(m, n)) time. Our approach first of all, in a preprocessing phase,
computes in O(m n log α(m, n)) time all the replacement shortest paths from
the source after the failure of every edge of T [13]. Then, the algorithm will run
through n − 1 phases, each returning in O(m) time a BSE for a failing edge
of T , as described in the following. Thus, the overall time complexity will be
dominated by the preprocessing step.
Let us fix e = (a, b) ∈ E(T ) as the failing edge of T . The idea is to show that,
after a O(n) preprocessing time, we can compute the avg-stretch λ(f ) of any f
in constant time. This immediately implies that we can compute a BSE for e by
looking at all O(m) swap edges for e.
Let U = V (Tb ) and let y be a node in U , we define:
M (y) =

X dT (y, v)
dG−e (s, v)

v∈U

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

and
Q=

X
v∈U

9

1
.
dG−e (s, v)

Let f = (x, y) be a candidate swap edge incident in y ∈ U . The avg-stretch of f
can be rewritten as:

λ(f ) =

X dT (s, x) + w(f ) + dT (y, v)

= dT (s, x) + w(f ) Q + M (y).
dG−e (s, v)

v∈U

Hence, the avg-stretch of f can be computed in O(1) time, once Q and M (y)
are available in constant time. Observe that Q does not depend on y and can
be computed in O(n) time. The rest of this section is devoted to show how to
compute M (y) for every y ∈ U in O(n) overall time.
Computing M (y) for all y ∈ U. Let y e y 0 be two nodes in
PU such that y
is a child of y 0 in T . Moreover, let Uy = V (Ty ), and let Qy = v∈Uy dG−e1(s,y) .
Hence, we can rewrite M (y) and M (y 0 ) as follows:
M (y) =

X
v∈Uy

and
M (y 0 ) =

dT (y, v)
+
dG−e (s, v)

X
v∈U −Uy

X w(y, y 0 ) + dT (y, v)
+
dG−e (s, v)

v∈Uy

w(y, y 0 ) + dT (y 0 , v)
dG−e (s, v)
X
v∈U −Uy

dT (y 0 , v)
.
dG−e (s, v)

Therefore, we have:


M (y) = M (y 0 ) + w(y, y 0 ) − Qy + (Q − Qy ) = M (y 0 ) + w(y, y 0 ) Q − 2Qy . (1)
The above equation implies that M (y) can be computed in O(1) time, once
we have computed M (y 0 ), Q and Qy . As a consequence, we can compute all
the M (y)’s as follows. First, we compute Qy for every y ∈ D in O(n) overall
time by means of a postorder visit of Tb . Notice also that Q = Qb . Then, we
compute M (b) explicitly in O(n) time. Finally, we compute all the other M (y)’s
by performing a preorder visit of Tb . When we visit a node y, we compute M (y)
in constant time using (1). Thus, the visit will take O(n) time. We have proved
the following:
Theorem 2. There exists an algorithm that solves the ABSE-AS problem in
O(mn log α(m, n)) time.

5

An approximate solution for ABSE-MS

In this section we show that for the max-stretch measure we can compute in
an almost linear O(m log α(m, n)) time, a set of good swap edges (GSE), each

10

Davide Bilò et al.

e

t

t0

0

f

t
z

A
y

B

C

B
t

e

0

y

f

D

C
y

g

0

A
y g

D

z

Fig. 2. The figure shows the two cases of the analysis, on the left t is an ancestor of
t0 , while on the right the opposite holds. The splines denote a path, while the straight
lines represent a single edge.

of which guarantees a relative approximation factor on the maximum stretch of
3/2 (tight), as opposed to that provided by the corresponding BSE. Moreover,
as shown in the next section, each GSE still guarantees an absolute maximum
stretch factor w.r.t. the paths emanating from the source (in the surviving graph)
equal to 3 (tight).
Lemma 3. Let e be a failing edge in T , let

g = (x, y) ∈ arg 0 min
dT (s, x0 ) + w(x0 , v 0 ) ,
0
(x ,v )∈C(e)

and, finally, let f = (x0 , y 0 ) be a best swap edge for e w.r.t. ABSE-MS. Then,
µ(g)/µ(f ) ≤ 3/2.
Proof. Let z be the critical node for the good swap edge g, and let t (resp., t0 )
denote the least common ancestor in T between y 0 and z (resp., y 0 and y). Let
D = dT (s, x) + w(x, y) = dG−e (s, y). By choice of g, it holds that dG−e (s, z) ≥ D
and dG−e (s, y 0 ) ≥ D. We divide the proof into the following two cases, as depicted
in Figure 2: either (1) t is an ancestor of t0 in T , or (2) t0 is an ancestor of t
in T . Let A, B, C denote the distance in T between y and t0 , t0 and t, t and z,
respectively.
Case 1 Since t is an ancestor of t0 (left side of Figure 2), we have that dTe/f (s, y) ≥
D + A and we can write:
σG−e (Te/f , y) ≥

D+A
D+A
D+A
=
≥
,
dG−e (s, y)
D
dG−e (s, z)

and similarly σG−e (Te/f , z) ≥ dD+B+C
. Moreover, by the definition of µ(·) we
G−e (s,z)
have that µ(f ) ≥ max{σG−e (Te/f , y), σG−e (Te/f , z)}. The previous inequalities
together imply:
σG−e (Te/g , z)
µ(g)
A+B+C +D
≤
≤
µ(f )
max{σG−e (Te/f , y), σG−e (Te/f , z)}
D + max {A, B + C} .

(2)

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

11

Now we divide the proof into two subcases, depending on whether B + C ≥ A
or B + C < A. Observe that D ≥ dG (s, y) ≥ A. If B + C ≥ A, then (2) becomes:
µ(g)
A+B+C +D
A
A
3
≤
=1+
≤1+
= ,
µ(f )
B+C +D
B+C +D
2A
2
otherwise, if B + C < A, then (2) becomes:
µ(g)
A+B+C +D
2A + D
A
A
3
≤
<
=1+
≤1+
= .
µ(f )
A+D
A+D
A+D
2A
2
Case 2 Assume now that t0 is an ancestor of t (right side of Figure 2). Since
µ(f ) ≥ σG−e (Te/f , y) ≥

dG−e (s, y 0 ) + A + B
dG−e (s, y 0 ) + A + B
=
,
dG−e (s, y)
D

we have that:
µ(g)
A+B+C +D
≤
µ(f )
dG−e (s, z)
A+B+C +D
≤
dG−e (s, z)

D
dG−e (s, y 0 ) + A + B
D
·
A+B+D
·

and since dG−e (s, z) ≥ dG (s, z) ≥ C, and recalling that dG−e (s, z) ≥ D, we have:


A+B+C +D
D
C
D
µ(g)
≤
·
= 1+
·
. (3)
µ(f )
A+B+D
max {C, D}
A+B+D
max {C, D}
Moreover, notice that also the following holds:
µ(g)
µ(g)
A+B+C +D
dG−e (s, z)
≤
≤
·
µ(f )
σG−e (Te/f , z)
dG−e (s, z)
dG−e (s, y 0 ) + dT (y 0 , t) + C
A+B
A+B+C +D
=1+
.
≤
C +D
C +D

(4)

We divide the proof into the following two subcases, depending on whether
D ≥ C or D < C. In the first subcase, i.e., D ≥ C, we have that (3) becomes
µ(g)
C
µ(f ) ≤ 1 + A+B+D , and hence, by combining this inequality with (4), we obtain:

C
A+B
,
A+B+D C +D


C
A+B
1
3
≤ 1 + min
,
≤1+ = .
A+B+C
2C
2
2

µ(g)
≤ 1 + min
µ(f )



In the second subcase, i.e., D < C, (3) becomes:


C
D
D
D
D
µ(g)
≤ 1+
·
≤
+
<1+
,
µ(f )
A+B+D
C
C
A+B+D
A+B+D

(5)

12

Davide Bilò et al.

f

D+

D+

D
g

e
y0 = b
D

0

z

y

D
g

Fig. 3. A tight example showing that the quality of the good swap edge g computed by
the algorithm is a factor of 3/2 away from the qualify of a best swap edge f . In the
picture, it is assumed that the distance from s to b is equal to 0, while the three dashed
edges are assumed to be incident to the source, and the labels correspond to their weight.
3D
Then, µ(f ) = σG−e (Te/f , y) = 2D+
' 2, while µ(g) = σG−e (Te/g , z) = D+
' 3, for
D
small values of .

and hence, by combining (5) and (4), we have that:


µ(g)
D
A+B
≤ 1 + min
,
µ(f )
A+B+D C +D


D
A+B
1
3
≤ 1 + min
,
≤1+ = ,
A + B + D 2D
2
2
from which the claim follows.

t
u

Given the result of Lemma 3, we can derive an efficient algorithm to compute
all the GSE for ABSE-MS. More precisely, in [18] it was shown how to find them
in O(m α(m, n)) time. Essentially, the approach used in [18] was based on a
reduction to the SPT sensitivity analysis problem [20]. However, in [19] it was
proposed a faster solution to such a problem, running in O(m log α(m, n)) time.
Thus, we can provide the following
Theorem 3. There exists a 3/2-approximation algorithm that solves the ABSE-MS
problem in O(m log α(m, n)) time.
We conclude this section with a tight example which shows that the analysis
provided in Lemma 3 is tight (see Figure 3).

6

Quality analysis

As for previous studies on swap edges, it is interesting now to see how the tree
obtained from swapping a failing edge e = (a, b) with its BSE f compares with
a true SPT of G − e. According to our swap criteria, we will then analyze the
lower and upper bounds of the max- and avg-stretch of f , i.e., µ(f ) and λ(f ),
respectively.
As already observed in the introduction, it is well-known [18] that for the swap
edge, say g, which belongs to the shortest path in G − e between s and the root of

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

Non-tree 
edges of
weight 
D + 2
to all the
leaves

13

s=a
e
b
D

D

D

D

f
y
|
{z
}

Many leaves at distance D

x

Fig. 4. Tight ratios for µ(f ) and λ(f ). In the picture, the SPT T (solid edges) along
with the removed edge e = (a, b) of weight 0; non-tree edges are dashed and the best
swap edge (for both the maximum and the average stretch) is easily seen to be f = (x, y),
of weight  > 0. Then, we have that µ(f ) = 3D+
, which tends to 3 for small values of
D+2
, while λ(f ) tends to 3 as well, as soon as the number of leaves grows. Notice that f is
also a good swap edge for e.

the detached subtree Tb , we have that for any v ∈ V (Tb ), σG−e (Te/g , v) ≤ 3. This
immediately implies that µ(g), λ(g) ≤ 3, namely µ(f ), λ(f ) ≤ 3. These bounds
happen to be tight, as shown in Figure 4.
Let us now analyze the lower and upper bounds of the max-stretch of a good
swap edge g, i.e., µ(g), as defined in the previous section. First of all, once again
it was proven in [17] that for any v ∈ V (Tb ), σG−e (Te/g , v) ≤ 3, which implies
that µ(g) ≤ 3. Moreover, the example shown in Figure 4 can be used to verify
that this bound is tight.

7

Conclusions

In this paper we have studied two natural SPT swap problems, aiming to
minimize, after the failure of any edge of the given SPT, either the maximum or
the average stretch factor induced by a swap edge. We have first proposed two
efficient algorithms to solve both problems. Then, aiming to the design of faster
algorithms, we developed for the maximum-stretch measure an almost linear
algorithm guaranteeing a 3/2-approximation w.r.t. the optimum.
Concerning future research directions, the most important open problem
remains that of finding a linear-size edge-fault-tolerant SPT with a (maximum)
stretch factor w.r.t. the root better than 3, or to prove that this is unfeasible.
Another interesting open problem is that of improving the running time of
our exact solutions. Notice that both our exact algorithms pass through the
computation of all the post-failure single-source distances, and if we could avoid
that we would get faster solutions. At a first glance, this sounds very hard, since

14

Davide Bilò et al.

the stretches are heavily dependant on post-failure distances, but, at least in
principle, one could exploit some monotonicity property among swap edges that
could allow to skip such a bottleneck. Besides that, it would be nice to design
a fast approximation algorithm for the average-stretch measure. Apparently, in
this case it is not easy to adopt an approach based on good swap edges as for
the maximum-stretch case, since swap edges optimizing other reasonable swap
criteria (e.g., minimizing the distance towards the root of the detached subtree,
or minimizing the distance towards a detached node) are easily seen to produce
an approximation ratio of 3 as opposed to a BSE. A candidate solution may
be that of selecting a BSE w.r.t. the sum-of-distances criterium, which can be
solved in almost linear time [8], but for which we are currently unable to provide
a corresponding comparative analysis.
Finally, we mention that a concrete task which will be pursued is that of
conducting an extensive experimental analysis of the true performances of our
algorithms, to check whether for real-world instances the obtained stretches are
sensibly better or not w.r.t. the theoretical bounds.

References
1. Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti.
A faster computation of all the best swap edges of a tree spanner. In Structural
Information and Communication Complexity - 22nd International Colloquium,
SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, pages 239–253, 2015.
2. Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti.
Improved purely additive fault-tolerant spanners. In Algorithms - ESA 2015 - 23rd
Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings,
pages 167–178, 2015.
3. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-tolerant
approximate shortest-path trees. In Algorithms - ESA 2014 - 22th Annual European
Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 137–148,
2014.
4. Davide Bilò, Luciano Gualà, and Guido Proietti. Finding best swap edges minimizing
the routing cost of a spanning tree. Algorithmica, 68(2):337–357, 2014.
5. Davide Bilò, Luciano Gualà, and Guido Proietti. A faster computation of all the
best swap edges of a shortest paths tree. Algorithmica, 73(3):547–570, 2015.
6. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault-tolerant
spanners for general graphs. In Proceedings of the 41st Annual ACM Symposium on
Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009,
pages 435–444, 2009.
7. Ajoy K. Datta, Lawrence L. Larmore, Linda Pagli, and Giuseppe Prencipe. Linear
time distributed swap edge algorithms. In Algorithms and Complexity, 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings,
pages 122–133, 2013.
8. Aleksej Di Salvo and Guido Proietti. Swapping a failing edge of a shortest paths
tree by minimizing the average stretch factor. Theor. Comput. Sci., 383(1):23–33,
2007.
9. Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and
simpler. In Proceedings of the 30th Annual ACM Symposium on Principles of

Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges

10.

11.

12.

13.
14.
15.
16.
17.
18.
19.

20.
21.

15

Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages
169–178, 2011.
Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Giuseppe Prencipe, and
Nicola Santoro. Efficient protocols for computing the optimal swap edges of a
shortest path tree. In Exploring New Frontiers of Theoretical Informatics, IFIP
18th World Computer Congress, TC1 3rd International Conference on Theoretical
Computer Science (TCS2004), 22-27 August 2004, Toulouse, France, pages 153–166,
2004.
Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Giuseppe Prencipe, and
Nicola Santoro. Point-of-failure shortest-path rerouting: Computing the optimal
swap edges distributively. IEICE Transactions, 89-D(2):700–708, 2006.
Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Computing all the best swap edges distributively. J. Parallel Distrib.
Comput., 68(7):976–983, 2008.
Luciano Gualà and Guido Proietti. Exact and approximate truthful mechanisms
for the shortest paths tree problem. Algorithmica, 49(3):171–191, 2007.
Giuseppe F. Italiano and Rajiv Ramaswami. Maintaining spanning trees of small
diameter. Algorithmica, 22(3):275–304, 1998.
Hiro Ito, Kazuo Iwama, Yasuo Okabe, and Takuya Yoshihiro. Single backup table
schemes for shortest-path routing. Theor. Comput. Sci., 333(3):347–353, 2005.
Camille Jordan. Sur les assemblages de lignes. J. Reine Angew. Math, 70(185):81,
1869.
Enrico Nardelli, Guido Proietti, and Peter Widmayer. A faster computation of the
most vital edge of a shortest path. Inf. Process. Lett., 79(2):81–85, 2001.
Enrico Nardelli, Guido Proietti, and Peter Widmayer. Swapping a failing edge of a
single source shortest paths tree is good and fast. Algorithmica, 35(1):56–74, 2003.
Seth Pettie. Sensitivity analysis of minimum spanning trees in sub-inverseAckermann time. In Algorithms and Computation, 16th International Symposium,
ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, pages
964–973, 2005.
Robert Endre Tarjan. Sensitivity analysis of minimum spanning trees and shortest
path trees. Inf. Process. Lett., 14(1):30–33, 1982.
Bang Ye Wu, Chih-Yuan Hsiao, and Kun-Mao Chao. The swap edges of a multiplesources routing tree. Algorithmica, 50(3):299–311, 2008.

