An Improved Algorithm for Computing All the
Best Swap Edges of a Tree Spanner
Davide Bilò1 , Feliciano Colella2 , Luciano Gualà3 , Stefano Leucci4 ,
and Guido Proietti5,6

arXiv:1710.01516v1 [] 4 Oct 2017

1
2
3
4
5
6

Università di Sassari, Italy. davide.bilo@uniss.it
Gran Sasso Science Institute, L’Aquila, Italy. feliciano.colella@gssi.it
Università di Roma “Tor Vergata”, Italy. guala@mat.uniroma2.it
ETH Zürich, Switzerland. stefano.leucci@inf.ethz.ch
Università degli Studi dell’Aquila, Italy. guido.proietti@univaq.it
Istituto di Analisi dei Sistemi ed Informatica, CNR, Roma, Italy.

Abstract
A tree σ-spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a
spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor
σ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or
even a good tree spanner is a very hard computational task. Thus, if one has to face a transient
edge failure in T , the overall effort that has to be afforded to rebuild a new tree spanner (i.e.,
computational costs, set-up of new links, updating of the routing tables, etc.) can be rather
prohibitive. To circumvent this drawback, an effective alternative is that of associating with each
tree edge a best possible (in terms of resulting stretch) swap edge – a well-established approach
in the literature for several other tree topologies. Correspondingly, the problem of computing
all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it
efficiently means to exploit the structure of shortest paths not only in G, but also in all the
scenarios in which an edge of T has failed. For this problem we provide a very efficient solution,
running in O(n2 log4 n) time, which drastically improves (almost by a quadratic factor in n in
dense graphs!) on the previous known best result.
1998 ACM Subject Classification G.2.2 [Graph Theory] Graph algorithms, Trees
Keywords and phrases Transient edge failure, Swap algorithm, Tree spanner

1

Introduction

The problem of computing all the best swap edges (ABSE) of a tree has a long and rich
algorithmic tradition. Basically, let G = (V (G), E(G), w) be an n-vertex and m-edge 2-edgeconnected undirected graph, with edge-weight function w : E(G) → R+ , and assume we
are given a spanning tree T of G, which was computed by addressing some criterion (i.e.,
objective function) φ. Then, the problem is that of computing a BSE for every edge e ∈ E(T ),
namely an edge f ∈ E(G) \ E(T ) such that the swap tree Te/f obtained by swapping e with
f in T optimizes some objective function φ0 out of all possible swap trees. Quite reasonably,
the function φ0 must be related (if not coinciding at all) with φ.
The first immediate motivation for studying an ABSE problem comes from the edge
fault-tolerance setting – a commonly accepted framework. Broadly speaking, the algorithmic
question here is to design sparse subgraphs that guarantee a proper level of functionality
even in the presence of an edge failure. In such a context, the rationale of an ABSE-based
solution is the following: operations are normally performed on a (possibly optimal) spanning

XX:2

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

tree, and whenever an edge failure takes place, a corresponding BSE is plugged in. This
way, the connectivity is reestablished in the most prompt and effective possible way (see
also [14, 20] for some additional practical motivations).
Besides their practical relevance, ABSE problems have also an interesting theoretical
motivation. Indeed, swapping can be reviewed as an exploration of the space of the perturbed
(w.r.t. an edge swap) solutions to a given spanning tree optimization problem. Thus, the
algorithmic challenge of solving efficiently an ABSE problem is related with the understanding
of the structure of this space of perturbed solutions. And this is exactly why each ABSE
problem has its own combinatorial richness, and thus requires a specific approach to be solved
efficiently. Then, different ABSE problems have required the use of completely different
approaches and methods in order to obtain efficient solutions. For instance, the most famous
and studied ABSE problem comes when T is a minimum spanning tree (MST) of G. In
this case, a best swap is of course a swap edge minimizing the cost (i.e., sum of the edge
weights) of the swap tree, i.e., a swap edge of minimum weight (and we know this produces
a MST of the perturbed graph). This problem is also known as the MST sensitivity analysis
problem, and can be solved in O(m log α(m, n)) time [19], where α denotes the inverse of the
Ackermann function, by using an efficient data structure, namely the split-findmin [12]. This
was improving on another efficient solution given by Tarjan [22], running in O(m α(m, n))
time and making use of the transmuter, namely a compact way of representing the cycles
of a graph. Other data structures which revealed their usefulness to solve efficiently ABSE
problems include kinetic heaps [6], top trees [3], mergeable heaps [18], and many others.
In this paper, we focus on the ABSE problem on the elusive spanning tree structure,
namely the tree spanner (ABSE-TS problem in the following). A tree spanner is built with
the aim of preserving node-to-node distances in G. Indeed, the stretch factor σ of a spanning
tree T of G is defined as the maximum, over all the pairs u, v ∈ V (G), of dT (u, v)/dG (u, v),
where dT and dG denote distances in T and G, respectively. Correspondingly, an optimal tree
spanner has minimum stretch out of all the spanning trees of G. Unfortunately, finding an
optimal tree spanner is notoriously an APX-hard problem, with no known o(n)-approximation.
Hence, once a given solution undergoes a transient edge failure, the recomputation from
scratch of a new (near) optimal solution is computationally unfeasible. Thus, swapping in
a tree spanner is even more attractive than in general, and indeed the ABSE-TS problem
was studied in [10], where the authors devised two solutions for both the weighted and
the unweighted case, running in O(m2 log n) and O(n3 ) time, respectively, and using O(m)
and O(n2 ) space, respectively. However, there the authors assume that a BSE is an edge
minimizing the stretch of the swap tree w.r.t. distances in the original graph G, and not in
the graph G deprived of e, say G − e. This contrasts with the general assumption (and the
intuition) that the quality of a swap tree should be evaluated in the surviving graph. Hence,
in [3] the authors resorted to such a standard setting, and provided two efficient linear-space
solutions for both the weighted and the unweighted case, running in O(m2 log α(m, n)) and
O(mn log n) time, respectively, and both using linear space. Notice that from a computational
point of view, as shown in [3], the two settings are substantially equivalent, so our solutions
can be used to improve the results given in [10] as well.

1.1

Our result

In this paper, we present a new algorithm that solves the ABSE-TS problem in O(n2 log4 n)
time and O(n2 + m log2 n) space. Thus, our solution improves on the running time of both
the algorithms provided in [3], for weighted and unweighted graphs, respectively, whenever
m = Ω(n log3 n). Most remarkably, for dense weighted graphs, the improvement is almost

D. Bilò et al.

quadratic in n.
To put into focus our result, it is worth noticing that, as observed in [10], the estimation
of the stretch of the swap tree induced by a single swap edge f for a given failing edge e,
would in principle ask for the evaluation of the stretch of O(m) relevant pairs of nodes in G,
namely the endvertices of all the non-tree edges that may serve as swap edge for e besides f .
And in fact, a critical edge for f is the one whose endvertices maximize such a stretch out of
these non-tree edges, and two swap edges will be essentially compared on the basis of their
stretch w.r.t. their critical edge. This is basically the reason why both previous approaches
take Ω(m2 ) time. Thus, to avoid such a bottleneck, we drastically reduce, on the one hand,
the number of candidate best swap edges, and on the other hand, the number of potential
critical edges that need to be checked. More precisely, for each of the n − 1 considered edges
in T , we succeed in reducing to O(n log n) the number of best swap edge candidates, and for
each one of them we just need to check O(log2 n) possible critical edges. The key ingredients
to reach such a goal are the following:
A centroid decomposition of T , which consists of a log-depth hierarchical decomposition
of the vertices in T ; a careful use of such a decomposition, combined with a set of
preprocessing steps that associate various information with the tree nodes, allows us to
reduce the number of candidate BSEs and of their corresponding candidate critical edges.
As far as we know, this is the first time that such a decomposition is used to solve an
ABSE problem, and we believe it will possibly be useful in other contexts as well.
The second ingredient is given by the dynamic maintenance of the upper envelopes of a
set of linear functions. Each of these functions is associated with a non-tree edge, and
whenever the failure of a given tree edge is considered, it expresses the stretch such a
non-tree edge induces w.r.t. a variable candidate BSE. This way, when we have to find
a critical edge for a given candidate BSE f , we have to select the maximum out of all
the functions once they are evaluated in f . In geometric terms, this translates into the
maintenance of the upper envelope of a set of functions, with the additional complication
that, for consistency reasons, this set of functions must be suitably partitioned into
groups according to the underlying centroid decomposition, and moreover these groups
are dynamic, since they depend on the currently considered tree edge.

1.2

Related work

The research on tree spanners is very active, also due to the strong relationship with the huge
literature on spanners, where distances in G are approximately preserved through a sparse
spanning subgraph. As mentioned before, finding an optimal tree spanner is a quite hard
problem. More precisely, on weighted graphs, if G does not admit a tree 1-spanner (i.e., a
spanning tree with σ = 1, which can be established in polynomial time [9]), then the problem
is not approximable within any constant factor better than 2, unless P=NP [16]. In terms of
approximability, no non-trivial upper bounds are known, except for the O(n)-approximation
factor returned by a minimum spanning tree (MST) of G. If G is unweighted, things go slightly
better. More precisely, in this case the problem becomes O(log n)-approximable, while unless
P=NP, the problem is not approximable within an additive term of o(n) [11]. Moreover, the
corresponding decision problem of establishing whether G admits a tree spanner with stretch
σ is NP-complete for every fixed σ ≥ 4 (for σ = 2 it is polynomial-time solvable [9], while for
σ = 3 the problem is open). Finally, it is known that constant-stretch tree spanners can be
found for several special classes of (unweighted) graphs, like strongly chordal, interval, and
permutation graphs (see [7] and the references therein).

XX:3

XX:4

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

Concerning the problem of swapping in spanning trees, this has received a significant
attention from the algorithmic community. There is indeed a line of papers that address
ABSE problems starting from different types of spanning trees. Just to mention a few, besides
the MST, we recall the minimum diameter spanning tree (MDST), the minimum routing-cost
spanning tree (MRCST), and the single-source shortest-path tree (SPT). Concerning the
MDST, a best swap is instead an edge minimizing the diameter of the swap tree [13, 17],
and the best solution runs in O(m log α(m, n)) time [6]. Regarding the MRCST, a best
swap is clearly an edge minimizing the all-to-all routing cost of the swap tree [23], and the
fastest solution for solving this problem has a running time of O m2O(α(n,n)) log2 n [5].
Concerning the SPT, the most prominent swap criteria are those aiming to minimize either
the maximum or the average distance from the root, and the corresponding ABSE problems
can be addressed in O(m log α(m, n)) time [6] and O(m α(n, n) log2 n) time [21], respectively.
Recently, in [4], the authors proposed two new criteria for swapping in a SPT, which are in a
sense related with this paper, namely the minimization of the maximum and the average
stretch factor from the root, for which they proposed an efficient O(mn + n2 log n) and
O(mn log α(m, n)) time solution, respectively.
Finally, for the sake of completeness, we mention that for the related concept of average
tree σ-spanners, where the focus is on the average stretch w.r.t. all node-to-node distances,
it was shown that every graph admits an average tree O(1)-spanner [1].

1.3

Preliminary definitions

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 (G), let E(X) be the set of edges incident to at least one vertex in
X. When X = {v}, we may write E(v) instead of E({v}). 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. Given an edge e ∈ E(T ), we let S(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. We also define S(e, X) = S(e) ∩ E(X), and S(e, X, Y ) = S(e) ∩ E(X) ∩ E(Y ). When
X = {v}, we will simply write S(e, v) in lieu of S(e, {v}). For any e ∈ E(T ) and f ∈ S(e),
let Te/f denote the swap tree obtained from T by replacing e with f .
Given two vertices x, y ∈ V (G), we denote by dG (x, y) the distance between x and y in G.
T (x,y)
We define the stretch factor of the pair (x, y) w.r.t. G and T as σG (T, x, y) = ddG
(x,y) . Accordingly, the stretch factor σG (T ) of T w.r.t. G is defined as σG (T ) = maxx,y∈V (G) σG (T, x, y).
I Definition 1 (Best Swap Edge). An edge f ∗ ∈ S(e) is a best swap edge (BSE) for e if
f ∗ ∈ arg minf ∈S(e) σG−e (Te/f ).
In the sequel, in order to solve the ABSE-TS problem, we will show how to efficiently find
a BSE for every edge e of a tree spanner T of G.

2

High-level description of the algorithm

It is useful to consider the tree T as rooted at any fixed vertex, and to assume, w.l.o.g., that
T is binary. Indeed, if T is not binary, then it is possible, by using standard techniques,
to transform G and T into an equivalent graph G0 and a corresponding binary spanning
tree T 0 , with |V (G0 )| = Θ(n) and |E(G0 )| = Θ(m), and such that a BSE for any edge of T

D. Bilò et al.

Algorithm: ABSE-TS(G, T )
1
2
3
4
5
6

7
8

T ← Centroid decomposition of T ;
foreach e ∈ E(T ) in postorder do
// n − 1 phases
Ue ← vertices of the component of T − e that contains the root of T ;
f ∗ ← ⊥;
// Current BSE for e
foreach v ∈ Ue do
// O(n) sub-phases
compute a v-BSE f for e and the corresponding stretch factor; // This takes O(log4 n)
time by using T and the dynamic maintenance of the upper envelopes
associated with the swap edges, as shown in Section 3
if σG−e (Te/f ) < σG−e (Te/f ∗ ) then f ∗ ← f ;
return f ∗ as BSE for e and continue with the next phase.

is univocally associated with a BSE for a corresponding edge of T 0 . This transformation
requires linear time and it is sketched in Appendix A for the sake of completeness.
As a preprocessing step, we compute a centroid decomposition of T . A centroid of an
n-vertex tree is a vertex whose removal splits T into subtrees of size at most n/2 [15]. A
centroid decomposition of T can be computed in O(n log n) time, and can be represented by
a tree T of height O(log n), whose nodes are actually subtrees of T . T is recursively defined
as follows: the root of T is T . Then, let τ be a node of T (i.e., a subtree of T ) such that τ
contains more than one vertex, and let c be a centroid of τ . Since T is binary, the forest τ − c
contains at most 3 trees, that we call τc1 , τc2 , and τc3 (if τ − c generates less than 3 subtrees,
we allow some τci to be the empty tree). Moreover, let τc0 be the subtree of T containing the
sole vertex c. Then, τ will have in T a child for each of the subtrees τci , i = 0, . . . , 3 (see
Figure 1 (a)). Since a centroid on a n-vertex tree can be found in linear time, the whole
procedure requires O(n log n) time, and it is easy to see that the height of T is O(log n).
Our solution (see Algorithm ABSE-TS) works in n − 1 phases, one for each tree edge as
considered in preorder w.r.t. T , and at the end of each phase returns a BSE for that edge.
Let e ∈ E(T ) be the currently considered edge, and let Ue (resp. De ) be the set of vertices
that belong to the connected component of T − e that contains (resp. does not contain) the
root of T . We break down each of these phases into O(n) additional sub-phases: when edge e
is failing, we consider all the vertices in Ue and, for each such vertex v, we solve a restricted
version of the ABSE-TS problem where we compute: (i) a v-restricted best swap edge (v-BSE
for short), i.e., an edge f ∈ arg minf ∈S(e,v) σG−e (Te/f ), and (ii) the corresponding stretch
factor σG−e (Te/f ). To simplify handling of special cases, whenever S(e, v) = ∅, we assume
that f = ⊥ and that σG−e (Te/f ) = +∞. As we will see in the rest of the paper, the core
of our algorithm is exactly the efficient computation of these v-BSEs and of their stretch
factors. This is done trough a clever selection of a small set of candidate v-BSEs, as we will
discuss in more detail in the next section. Once all the v-BSEs for e are computed, a BSE
for e can be found as the one minimizing the associated stretch factor.

3

Computing efficiently a v-BSE

To show how a v-BSE for e can be computed efficiently, we need some preliminary definitions:
I Definition 2 (Critical Edge). Given e ∈ E(T ) and a swap edge f = (v, u) ∈ S(e, v), a critical
dT (x, v) + w(f ) + dT (u, y)
edge 1 for f is an edge g = (x, y) ∈ S(e) maximizing φ(f, g) :=
.
w(g)
1

Notice that this definition does not contain dG−e (x, y) at the denominator, as expected, since it already
incorporates the property stated in the forthcoming Proposition 1.

XX:5

XX:6

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

Ue

v

c

x
e

τc1

τc2

e

De

y

f

De
f

g

f0

τc3

u

c

u

y

f0

c
u0

0

u
(a)

Ue

v

x
g

T
τc0

r

r

T

(b)

(c)

Figure 1 (a) An example of centroid decomposition of the tree T (which corresponds to the first
vertex of T ). (b) and (c): Two of the four possible cases situation illustrated in Lemma 4. The
subtree Tb is represented by the three gray triangles along with the vertex c. f is a swap edge for
e that minimizes w(f ) + dT (u, c), and g is its corresponding critical edge. The (c, y)-tree of Tb is
drawn in bold. Notice that f and g do not need to be incident to Tb.

I Definition 3 (Best Cut Edge). A v-best cut edge for e (v-BCE) is an edge f ∈ S(e, v)
minimizing ϕe (f ) = maxg∈S(e) φ(f, g).
Then, we will make use of the following property, which was given in [3]:
I Proposition 1. Every v-BCE for e is a v-BSE for e.
Let us first provide a high-level description of how we compute a v-BCE (i.e., a v-BSE)
for e. The algorithm will compute O(log n) v-BCE candidates, the best of which will be a
v-BCE for e. Informally speaking, each candidate f will be a swap edge close to the centroid
of a certain subtree Λ of T . Depending on the position of a critical edge for f , the algorithm
will recurse on a subtree of Λ and it will look for the next candidate. Thanks to the centroid
decomposition of T , the number of recursions/candidates will then be O(log n).
The key ingredient for the correctness of our algorithm is the next lemma. Given a
subtree Tb of T , a vertex c ∈ V (Tb), and a vertex y ∈ V (T ), consider the first vertex z of the
unique path from y to c in T that also belongs to V (Tb). The (c, y)−tree of Tb is defined as
follows: (1) if z = c, then it is the empty tree; otherwise (2) it is the tree of the forest Tb − c
that contains z. Then, the following holds (see also Figure 1 (b) and (c)):
I Lemma 4. Let Tb be a subtree of T such that V (Tb) ⊆ De , and let c ∈ V (Tb). Moreover, let
f = (v, u) ∈ S(e, v) be a swap edge for e that minimizes w(f ) + dT (u, c), and let g = (x, y)
be a critical edge for f . Assume that S(e, v, V (Tb)) contains a v-BCE for e. If f is not a
v-BCE for e, then S(e, v, V (T 0 )) contains a v-BCE for e, where T 0 is the (c, y)-tree of Tb.
Proof. Suppose that f is not a v-BCE for e, we will show that no swap edge f 0 = (v, u0 ) ∈
S(e, v) with u0 6∈ V (T 0 ) can be a v-BCE for e. Indeed:
dT (x, v) + w(f 0 ) + dT (u0 , y)
dT (x, v) + w(f 0 ) + dT (u0 , c) + dT (c, y)
=
w(g)
w(g)
dT (x, v) + w(f ) + dT (u, c) + dT (c, y)
≥
≥ φ(f, g) = ϕ(f ),
w(g)

ϕ(f 0 ) ≥ φ(f 0 , g) =

where we used the fact that dT (u0 , y) = dT (u0 , c) + dT (c, y) as either u0 = c or u0 and y are
in two different connected components of T − c.
J
Lemma 4 allows us to design a recursive algorithm for computing a v-BCE for e, whose key
steps are highlighted in Procedure FindBCE (notice that v and e are fixed). More precisely,

D. Bilò et al.

Procedure FindBCE(Λ)
1
2
3
4
5
6
7
8
9
10
11

if |V (Λ)| = 0 then return (⊥, ⊥) ;
c ← Centroid of Λ;
if c ∈ Ue then
τ ← unique child of Λ in T that contains all the vertices in V (Λ) ∩ De ;
return FindBCE (τ );
else
// c ∈ De
Compute an edge f = (v, u) ∈ arg min(v,u)∈S(e,v) {w(v, u) + dT (u, c)};
// See Appendix B
g1 = (x, y) ← FindCritical(f, T );
// Compute a critical edge for f (see Sec. 3.1)
τ ← (c, y)-tree of Λ;
// Either τ is empty or it is a child of Λ in T
(f 0 , g2 ) ← FindBCE (τ );
if φ(f, g1 ) ≤ φ(f 0 , g2 ) then return (f, g1 ); else return (f 0 , g2 );

the algorithm takes a tree Λ of the centroid decomposition T such that V (Λ) ∩ De 6= ∅, and
it computes a pair (f ∗ , g ∗ ) such that if S(e, v, V (Λ) ∩ De ) contains a v-BCE for e, then f ∗ is
a v-BCE for e, and g ∗ is its critical edge. Procedure FindBCE makes use of an additional
function FindCritical(f, T ) that returns a critical edge for f w.r.t. the failure of e. The
initial call will be FindBCE(T ). In order to handle base cases, we assume φ(⊥, ⊥) = +∞.
We now prove the correctness of the procedure:
I Lemma 5. Procedure FindBCE(T ) computes a v-BCE for e.
Proof. Consider an invocation of the procedure and let Λ and (f ∗ , g ∗ ) be its parameter
and the edges it returns, respectively. We prove the following claim by induction on the
cardinality of V (Λ): if S(e, v, V (Λ) ∩ De ) contains a v-BCE for e, then f ∗ is a v-BCE for e
and g ∗ is a critical edge for f ∗ .
If |V (Λ)| = 0, then the claim trivially holds. Otherwise, |V (Λ)| > 0, and we distinguish
two cases depending on the position of the centroid c of Λ. If c ∈ Ue , then there is only
one child τcj of Λ in T that contains all the vertices in V (Λ) ∩ De , as otherwise the vertices
in De would be disconnected in Λ. Hence, if S(e, v, V (Λ) ∩ De ) contains a v-BCE for e,
then S(e, v, V (τcj ) ∩ De ) also contains a v-BCE for e, and the claim follows by the inductive
hypothesis (as |V (τcj )| < |V (Λ)|). The remaining case is the one in which c ∈ De , here
the claim follows from Lemma 4 (where now Tb is the subtree of T induced by V (Λ) ∩ De )
together with the inductive hypothesis.
J
Next lemma provides an upper bound to the running time of the procedure:
I Lemma 6. Procedure FindBCE(T ) requires O((Γf + ΓFC ) log n) time, where Γf and ΓFC
is the time required to perform Steps 7 and 8, i.e., the time to find edge f , and to execute
Procedure FindCritical, respectively.
Proof. First of all, notice that Step 4 can be performed in O(1) time, after a O(log n)
preprocessing time in which we mark all the nodes of T on the path between the leaf of T
containing the lower vertex of e (which clearly belongs to De ) and the root of T . Then, we
only need to bound the depth of the recursion of the call FindBCE(T ). Observe that each
time Procedure FindBCE(Λ) recursively invokes itself on a tree Λ0 , we have that Λ0 is a child
of Λ in T . The claim follows since the height of T is O(log n).
J
Actually, the time to execute Step 7 is O(log n), after a preprocessing time and space of
O(n2 ), by making use of top-trees [2]. Due to space limitations, this result is postponed to
the appendix. On the other hand, Procedure FindCritical will require O(log3 n) time and
O(m log2 n) space, as we will show in the next two subsections.

XX:7

XX:8

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

Procedure FindCritical(f = (v, u), Λ)
1
2
3
4
5
6
7
8

if V (Λ) = {u} then return FindCriticalCandidate(f , T , Λ) ;
c ← Centroid of Λ;
Let j be the unique index in {0, 1, 2, 3} such that u ∈ V (τcj );
if c ∈ Ue then return FindCritical(f, τcj ) ;
G ← {FindCriticalCandidate(f, T, τci ) : i = 0, 1, 2, 3 ∧ i 6= j};
g1 ← arg maxg∈G φ(f, g);
g2 ← FindCritical(f, τcj );
return arg maxg∈{g1 ,g2 } {φ(f, g)};

3.1

// Here c ∈ De

Computing a critical edge for f

We will compute O(log2 n) critical edge candidates for f and we will show that a critical
edge for f will be one of them. More precisely, we look at O(log n) subtrees of the centroid
decomposition T and, for each such subtree Λ, we will consider O(log n) subtrees Ψ to find
a critical edge candidate having one endpoint in Ψ and the other in Λ. The choice of the
O(log2 n) pairs of trees is guided by the position of f , while the computation of a candidate
for a given pair (Ψ, Λ) is the core of the procedure and is described in the next subsection.
I Definition 7 ((Ψ, Λ)-Critical Edge). Given a failing edge e and a swap edge f = (v, u) ∈
S(e, v), and given two trees Ψ, Λ of the centroid decomposition T , a (Ψ, Λ)-critical edge for
f is an edge g = (x, y) ∈ arg maxg0 ∈S(e,V (Ψ)∩Ue ,V (Λ)∩De ) φ(f, g 0 ). When Ψ = T we will refer
to a (Ψ, Λ)-critical edge as a Λ-critical edge.
Let f = (v, u) ∈ S(e, v) and let Λ be a tree of the centroid decomposition T such that
u ∈ V (Λ). Procedure FindCritical returns a Λ-critical edge for f , when edge e fails (such
an edge always exists as f has one endpoint in Ue and the other in V (Λ) ∩ De ). Notice that
the call FindCritical(f, T ) in Procedure FindBCE computes a critical edge for f , since a
T -critical edge for f is actually a critical edge for f .
Procedure FindCritical uses as a subroutine Procedure FindCriticalCandidate(f , Ψ,
Λ), which for the sake of clarity will be described in the next subsection. For the moment, it
suffices to know that FindCriticalCandidate receives three inputs, i.e., edge f = (v, u) and
two subtrees Ψ, Λ of the centroid decomposition T such that v ∈ Ψ and, either u 6∈ V (Λ) or Λ
is the tree containing the sole vertex u, and it returns a (Ψ, Λ)-critical edge for f . If no such
edge exists, then FindCriticalCandidate returns ⊥ and we assume that φ(f, ⊥) = −∞.
I Lemma 8. Let f = (v, u) ∈ S(e, v), and let Λ be a tree of the centroid decomposition T
such that u ∈ V (Λ). Procedure FindCritical(f, Λ) returns a Λ-critical edge for f .
Proof. The proof is by induction on the cardinality of V (Λ).
If |V (Λ)| = 1, then the only vertex in Λ must be u and Procedure FindCritical invokes
Procedure FindCriticalCandidate(f, T, Λ). Hence, assuming such a procedure is correct,
it returns a (T, Λ)-critical edge, i.e., a Λ-critical edge. If |V (Λ)| > 1 then we distinguish two
cases, depending on the position of the centroid c of Λ.
If c ∈ De it is sufficient to notice that a Λ-critical edge for f must be incident to a tree τci
for some i = 0, 1, 2, 3. Let j be the unique index in {0, 1, 2, 3} such that u ∈ V (τcj ). If j 6= i
then, assuming Procedure FindCriticalCandidate is correct, it returns a (T, Λ)-critical
edge g1 (and hence a Λ-critical edge) for f . Procedure FindCritical then returns either g1
or another edge g such that φ(f, g) = φ(f, g1 ). If j = i, the algorithm is recursively invoked
and, since |V (τci )| < |V (Λ)| we know, by the induction hypothesis, that it correctly returns a
τci -critical edge for f , which is also Λ-critical edge for f .

D. Bilò et al.

XX:9

If c ∈ Ue , then we know that there is at most one τci containing one or more vertices in
De (as otherwise the vertices in V (Λ) ∩ De would be disconnected in Λ, a contradiction).
Moreover, since u ∈ V (Λ) ∩ De , there is exactly one such tree τci , namely τcj . The algorithm
recursively invokes itself on τcj and, since |V (τcj )| < |V (Λ)|, we know, by induction hypothesis,
that it returns a τcj -critical edge for f , which is also Λ-critical edge for f .
J
I Lemma 9. Procedure FindCritical(f, Λ) requires O(ΓFCC · log n) time, where ΓFCC is the
time required by an invocation of Procedure FindCriticalCandidate.
Proof. Notice that Procedure FindCritical performs exactly one recursive invocation for
each vertex of the tree T on the unique path between the root of T and u in T . The claim
follows since the height of T is O(log n).
J
In the next subsection, we show that ΓFCC = O(log2 n), and then we give our final result.

3.2

Procedure FindCriticalCandidate

In this subsection, we describe the core of the procedure that computes a critical edge for f .
Let us first describe informally the main idea of this part. Let b ∈ Ue and c ∈ De , and consider
any two edges f = (v, u), g = (x, y) ∈ S(e) such that b (resp. c) is on the unique path from x
to v (resp. from y to u) in T (see Figure 2). It turns out that the stretch factor of any f w.r.t.
a given g can be though as a linear function Φb,c,g (t) = αb,c (g) · t + βb,c (g), where αb,c (g)
and βb,c (g) only depend on g. More precisely, we will have that φ(f, g) = Φb,c,g (tb,c (f )), for
a suitable value tb,c (f ) which only depends on f . Hence, whenever we look for a critical
edge for f , we can ask for a corresponding function Φb,c,g (t) with maximum value on tb,c (f ).
Since we do not know a priori the edge f for which we need to compute a critical edge, we
will maintain this information as the upper envelope of a suitable set of functions. Let us
make this idea more precise.
I Definition 10 (Upper Envelope). Let F = {Φ1 , Φ2 , . . . , Φ` } be a finite set of functions,
where Φi : R → R for every i = 1, 2, . . . , `. The upper envelope of F is defined as UEF : t ∈
R 7→ arg max Φ(t) ∈ 2F .
Φ∈F

Let b ∈ Ue and c ∈ De . Given an edge f = (v, u), define tb,c (f ) as the quantity
1
dT (b, v) + w(f ) + dT (u, c). Given an edge g = (x, y), define αb,c (g) = w(g)
and βb,c (g) =
dT (x,b)+dT (c,y)
.
w(g)

Notice how, once b and c are fixed, tb,c (f ) only depends on f while αb,c (g)
and βb,c (g) only depend on g. Let Φb,c,g (t) = αb,c (g) · t + βb,c (g).
I Lemma 11. Let f = (v, u) ∈ S(e, v). Let b ∈ Ue and c ∈ De . Let X (resp. Y ) be a set of
vertices x ∈ Ue (resp. y ∈ De ) such that vertex b (resp. c) is on the unique path from x to v
(resp. from y to u) in T . For every g ∈ S(e, X, Y ) we have φ(f, g) = Φb,c,g (tb,c (f )).
Proof. Let g = (x, y). We have:
dT (x, v) + w(f ) + dT (u, y)
dT (x, b) + dT (b, v) + w(f ) + dT (u, c) + dT (c, y)
=
w(g)
w(g)
dT (b, v) + w(f ) + dT (u, c) dT (x, b) + dT (c, y)
=
+
= αb,c (g)tb,c (f ) + βb,c (g)
w(g)
w(g)

φ(f, g) =

= Φb,c,g (tb,c (f )).

J

I Definition 12 (Parent centroid). Let τ be a tree of the centroid decomposition T . The
parent centroid of τ is the centroid of the parent of τ in T .

XX:10

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

v

Ue

b
x Ψ

f
e

g
u

y

c

De

Figure 2 Illustration of Lemma 13.
f is a swap edge for e, Ψ and Λ are two
trees of the centroid decomposition, and
b and c are their corresponding parent
centroids. g is a potential (Ψ, Λ)-critical
edge for f . Notice that the unique path
from x to v (resp. from y to u) passes
through b (resp. c).

Λ

Lemma 11 is instrumental to proving the following (see Figure 2):
I Lemma 13. Let f = (v, u) ∈ S(e, v), and let Ψ, Λ be two trees of the centroid decomposition
of T such that the following conditions hold: (i) v 6∈ V (Ψ) or V (Ψ) = {v}, and (ii) u 6∈ V (Λ)
or V (Λ) = {u}. Let b (resp. c) be the parent centroid of Ψ (resp. Λ), and assume that
b ∈ Ue (resp. c ∈ De ). Then, an edge g is a (Ψ, Λ)-critical edge for f if and only if
Φb,c,g ∈ UEF (tb,c (f )) where F = {Φb,c,g0 : g 0 ∈ S(e, V (Ψ) ∩ Ue , V (Λ) ∩ De )}.
Proof. First of all we show the following property of the centroid decomposition T : let
p, q ∈ V (T ), and suppose that the unique path in T between the leaf nodes associated with
p and q contains a node whose corresponding centroid is z. Then, the unique path between
p and q in T contains z. Indeed, if z is either p or q, the property is trivially true. On the
other hand, suppose that z 6∈ {p, q}, and let τ be the subtree of T associated with z in T .
Then, let τzi be the child subtree of τ containing p. Observe that q is not in τzi . Moreover, by
construction, each path from a node of τzi , and in particular from p, to any node outside τzi ,
and in particular to q, must pass through z.
We now prove the claim. If V (Ψ) = {v} (resp. V (Λ) = {u}) then it follows from
Lemma 11 by choosing X = {v} and Y = V (Λ) ∩ De (resp. X = V (Ψ) ∩ Ue and Y = {u}).
The complementary case is the one in which v 6∈ V (Ψ) and u 6∈ V (Λ). Consider the vertices
v and b (resp. u and c) in T and notice that v (resp. u) cannot be an ancestor of b (resp. c).
Indeed, if that were the case, then the subtree of T induced by the vertices in V (Ψ) (resp.
V (Λ)) would contain b (resp. c) contradicting the hypothesis. Hence, the path from any
vertex in V (Ψ) to v (resp. V (Λ) to u) traverses b (resp. c) in T and therefore the same holds
in T . The claim follows by invoking Lemma 11 with X = V (Ψ) ∩ Ue and Y = V (Λ) ∩ De . J
Lemma 13 allows us to design a recursive procedure to compute a (Ψ, Λ)-critical edge
for f (see Procedure FindCriticalCandidate). To this aim we will make use of a data
structure Qe that, for each edge f ∈ S(e), and for each pair of trees Ψ, Λ of the centroid
decomposition, can perform a query operation that we name Qe (f, Ψ, Λ). This query reports
an edge whose function Φb,c,g is in UEF (tb,c (f )) where b and c are the parent centroids of Ψ
and Λ, respectively, and F = {Φb,c,g0 : g 0 ∈ S(e, V (Ψ) ∩ Ue , V (Λ) ∩ De )}.
Next two lemmas show the correctness and the running time of the procedure:
I Lemma 14. Let be given an edge f = (v, u) ∈ S(e, v) and two trees Ψ, Λ of the centroid
decomposition such that: (i) v ∈ V (Ψ), and (ii) u 6∈ V (Λ) or V (Λ) = {u}. Then, Procedure FindCriticalCandidate(f, Ψ, Λ) computes a (Ψ, Λ)-critical edge for f .
Proof. First of all notice that if V (Λ) ∩ De = ∅, then the algorithm correctly returns ⊥. We
now prove the claim by induction on |V (Ψ)|. If |V (Ψ)| = 1, then the only vertex in Ψ must
be v and Procedure FindCriticalCandidate queries Qe for Qe (f, Ψ, Λ). By Lemma 13,
the returned edge is a (Ψ, Λ)-critical edge for f . If |V (Ψ)| > 1 then we distinguish two
cases, depending on the position of the centroid b of Ψ. If b ∈ Ue it is sufficient to notice

D. Bilò et al.

XX:11

Procedure FindCriticalCandidate(f = (v, u), Ψ, Λ)
1
2
3
4
5
6
7
8
9

if V (Λ) ∩ De = ∅ then return ⊥;
if V (Ψ) = {v} then return Qe (f, Ψ, Λ);
b ← Centroid of Ψ;
Let j be the unique index in {0, 1, 2, 3} such that v ∈ V (τbj );
if b ∈ De then return FindCriticalCandidate(f, τbj , Λ);
G ← {Qe (f, τbi , Λ) : i = 0, 1, 2, 3 ∧ i 6= j};
g1 ← arg maxg∈G φ(f, g);
g2 ← FindCriticalCandidate(f, τbj , Λ);
return arg maxg∈{g1 ,g2 } {φ(f, g)};

// Here b ∈ Ue

that a (Ψ, Λ)-critical edge for f must be incident to a tree τbi for some i = 0, 1, 2, 3. Let j
be the unique index in {0, 1, 2, 3} such that v ∈ V (τbj ). If j 6= i then, by Lemma 13, the
query Qe (f, τbi , Λ) returns a (τbi , Λ)-critical edge g 0 (and hence g 0 is also a (Ψ, Λ)-critical
edge) for f . Procedure FindCritical then returns either g 0 or another edge g such that
φ(f, g) = φ(f, g 0 ). If j = i, the algorithm is recursively invoked and, since |V (|τbi |)| < |V (Ψ)|
we know, by the induction hypothesis, that it returns a (τbi , Λ)-critical edge for f , which is
also (Ψ, Λ)-critical edge for f . If b ∈ De , then there is at most one τbi containing at least one
vertex in Ue (as the converse would imply that the vertices in V (Ψ) ∩ Ue are disconnected in
Ψ, a contradiction). Moreover, since v ∈ V (Ψ) ∩ Ue , there is exactly one such tree τbi , namely
τbj . The algorithm recursively invokes itself on τbj and we know, by induction hypothesis,
that it returns a τbj -critical edge for f , which is also (Ψ, Λ)-critical edge for f .
J
I Lemma 15. Procedure FindCriticalCandidate(f, Ψ, Λ) requires O(ΓQe · log n) time,
where ΓQe is the time required by a query on Qe .
Proof. Notice that Procedure FindCriticalCandidate performs exactly one recursive invocation for each vertex of the tree T on the unique path between the root of T and u in T .
The claim follows since the height of T is O(log n).
J
Thus, to get the promised running time of O(log2 n) for ΓFCC , we are left to prove that
ΓQe = O(log n). Actually, such a bound can be obtained by suitably implementing Qe in
such a way that all the underlying upper envelope functions are efficiently maintained. Due
to space limitation, this technical part is postponed to the appendix. By combining all the
lemmas, and by observing that we need O(n2 ) space to handle the top-trees, and O(m log2 n)
space to implement each Qe (as shown in the appendix), we eventually can give the following:
I Theorem 16. The ABSE-TS problem can be solved in O(n2 log4 n) time and O(n2 +m log2 n)
space.
References
1

2

3

Ittai Abraham, Yair Bartal, and Ofer Neiman. Embedding metrics into ultrametrics and
graphs into spanning trees with constant average distortion. In Proc. of the 18th Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 502–511, 2007.
Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms,
1(2):243–264, 2005. doi:10.1145/1103963.1103966.
Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. A
faster computation of all the best swap edges of a tree spanner. In Proc. of the 22nd Intl.
Colloquium Structural Information and Communication Complexity, pages 239–253, 2015.
doi:10.1007/978-3-319-25258-2_17.

XX:12

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

4

5

6

7

8
9
10
11
12

13
14

15
16
17

18

19

20

21

22
23

Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. Effective
edge-fault-tolerant single-source spanners via best (or good) swap edges. In Proc. of the
24th Intl. Colloquium Structural Information and Communication Complexity, in press.
Davide Bilò, Luciano Gualà, and Guido Proietti. Finding best swap edges minimizing
the routing cost of a spanning tree. Algorithmica, 68(2):337–357, 2014. doi:10.1007/
s00453-012-9674-y.
Davide Bilò, Luciano Gualà, and Guido Proietti. A faster computation of all the best
swap edges of a shortest paths tree. Algorithmica, 73(3):547–570, 2015. doi:10.1007/
s00453-014-9912-6.
Andreas Brandstädt, Victor Chepoi, and Feodor F. Dragan. Distance approximating trees
for chordal and dually chordal graphs. J. Algorithms, 30(1):166–184, 1999. doi:10.1006/
jagm.1998.0962.
Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In Proc. of the 43rd
Annual IEEE Symposium on Foundations of Computer Science, pages 617–626. IEEE, 2002.
Leizhen Cai and Derek G. Corneil. Tree spanners. SIAM J. Discrete Math., 8(3):359–387,
1995. doi:10.1137/S0895480192237403.
Shantanu Das, Beat Gfeller, and Peter Widmayer. Computing all best swaps for minimumstretch tree spanners. J. Graph Algorithms Appl., 14(2):287–306, 2010.
Yuval Emek and David Peleg. Approximating minimum max-stretch spanning trees on
unweighted graphs. SIAM J. Comput., 38(5):1761–1781, 2008. doi:10.1137/060666202.
Harold N. Gabow. A scaling algorithm for weighted matching on general graphs. In Proc.
of the 26th Annual Symposium on Foundations of Computer Science, pages 90–100, 1985.
doi:10.1109/SFCS.1985.3.
Giuseppe F. Italiano and Rajiv Ramaswami. Maintaining spanning trees of small diameter.
Algorithmica, 22(3):275–304, 1998. doi:10.1007/PL00009225.
Hiro Ito, Kazuo Iwama, Yasuo Okabe, and Takuya Yoshihiro. Polynomial-time computable
backup tables for shortest-path routing. In Proc. of the 10th Intl. Colloquium Structural
Information and Communication Complexity, pages 163–177, 2003.
Camille Jordan. Sur les assemblages de lignes. J. Reine Angew. Math, 70(185):81, 1869.
Christian Liebchen and Gregor Wünsch. The zoo of tree spanner problems. Discrete Applied
Mathematics, 156(5):569–587, 2008. doi:10.1016/j.dam.2007.07.001.
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. doi:10.1016/
S0020-0190(00)00175-7.
Enrico Nardelli, Guido Proietti, and Peter Widmayer. Nearly linear time minimum spanning tree maintenance for transient node failures. Algorithmica, 40(2):119–132, 2004.
doi:10.1007/s00453-004-1099-9.
Seth Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time.
In Proc. of the 16th Intl. Symposium on Algorithms and Computation, pages 964–973, 2005.
doi:10.1007/11602613_96.
Guido Proietti. Dynamic maintenance versus swapping: An experimental study on shortest
paths trees. In Proc. of the 4th Intl. Workshop on Algorithm Engineering, pages 207–217,
2000. doi:10.1007/3-540-44691-5_18.
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. doi:
10.1016/j.tcs.2007.03.046.
Robert Endre Tarjan. Sensitivity analysis of minimum spanning trees and shortest path
trees. Inf. Process. Lett., 14(1):30–33, 1982. doi:10.1016/0020-0190(82)90137-5.
Bang Ye Wu, Chih-Yuan Hsiao, and Kun-Mao Chao. The swap edges of a multiple-sources
routing tree. Algorithmica, 50(3):299–311, 2008. doi:10.1007/s00453-007-9080-z.

D. Bilò et al.

A

XX:13

Reducing the degree of T

Here we show a linear time reduction that transforms G and a rooted spanning tree T of G
into an equivalent graph G0 = (V (G0 ), E(G0 ), w) and a corresponding binary spanning tree
T 0 such that |V (G0 )| = Θ(n) and |E(G0 )| = Θ(m).
Initially, G0 , w0 , and T 0 coincide with G, w, and T , respectively. We iteratively search for
a vertex u in T 0 that has 3 or more children, and we lower its degree. Let v1 , . . . , vh , with
h ≥ 3, be the children of u. We remove all the edges {(u, vi ) : 1 ≤ i ≤ h} from both G0 and
T 0 , then we add to both G0 and T 0 a binary tree whose root coincides with u, and that has
exactly h leaves x1 , . . . , xh . We assign weight w0 (e) = 0 to all the edges e of this tree. Finally,
we add to G0 and T 0 an edge (xi , vi ) for each 1 ≤ i ≤ h, and we set w0 (xi , vi ) = w(u, vi ). An
example of such a transformation is shown in Figure 3.

G

G0

u

u
xi
vi
vi
(a)

(b)

Figure 3 Reducing the degree of vertices in G: on the left side, the tree T (solid edges) embedded
in G, on the right side the superimposition of the binary tree to T in order to get a maximum degree
of 3. Solid edges in the gray area have weight 0, while the weight of (xi , vi ) is w(u, vi ).

Clearly, |V (G0 )| = O(|V (G)|), |E(G0 )| = O(|E(G)|), and, moreover, the computation
of G0 and T 0 requires linear time. Now, observe that, for every a, b ∈ V (G), it holds that
0
dTe/f (a, b) = dTe/f
(a, b). Furthermore, for every edge e = (u, vi ) of T , f is a swap edge for e
in T iff f is a swap edge for the edge (z, vi ) in T 0 , where z is the parent of vi in T 0 . As a
consequence, we can conclude that, for every edge e = (u, vi ) of T , f ∈ S(e) is a BSE for e
w.r.t. T iff f is a BSE for the edge (z, vi ) w.r.t. T 0 , where z is the parent of vi in T 0 .

B

Selecting edge f in Step 7 of Procedure FindBCE(Λ)

In this section we show how to efficiently find an edge f = (v, u) ∈ S(e) minimizing
w(f ) + dT (u, c), where c is a vertex in De , as Procedure FindBCE requires. We will show how
this problem can be solved by using top-trees [2].
A top-tree is a dynamic data structure that maintains a (weighted) forest F of trees
under link (i.e., edge-insertion) and cut (i.e., edge-deletion) operations. Moreover, some of
the vertices of F can be marked and the top-tree is able to perform closest marked vertex
(CMV, for short) queries, i.e., it can report the marked vertex that is closest to a given vertex
z. A top-tree on n vertices can be built in linear time and each of all the aforementioned
operations requires O(log n) time.
We maintain a top-tree Υv of size O(n) for each vertex v ∈ V (T ), and so we use a total of
O(n2 ) space. Each of these top-trees is the tree T augmented with some additional marked

XX:14

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
v

T

Υv
f

e

e

u
w(f )

u
(a)

u
(b)

Figure 4 (a) The subtree of T induced by De along with swap edges in S(e, v), and (b) the
corresponding top-tree Υv . The black vertices of Υv are the same of the tree T . For each u ∈ V (T )
such that f = (v, u) ∈ S(e, v), Υv contains an additional vertex u (shown as a white square), and a
corresponding edge (u, u) with weight w(f ).

vertices. More precisely, for each v ∈ V (T ) and for each edge f = (v, u) ∈ E(G) \ E(T ) we
add to Υv a marked vertex u and the edge (u, u) with a weight of w(f ) (see Figure 4).
Whenever we are finding a v-BSE for e and we need to find the edge f minimizing
w(f ) + dT (u, c) we do the following: (i) we cut the edge e from Υv , (ii) we perform a CMV
query on Υv to find the closest marked vertex u to c, if any, (iii) we undo the cut operation
by linking the endpoints of e in Υv , and finally (iv) we return the edge (v, u) (or ⊥ if no u
has been found).
I Lemma 17. Let e ∈ E(T ) be a failing edge and let c ∈ De . An edge f = (v, u) ∈ S(e, v)
minimizing w(f ) + dT (u, c) can be found in O(log n) time. Moreover, all the top-trees Υv
can be initialized in O(n2 ) time.
Proof. Each of the n top-trees Υv can be built in time O(n) by explicitly considering all
the edges in E(v) (notice that Υv contains at most 2n vertices as there can be at most one
marked vertex per vertex in V (T )).
As for the time complexity of finding edge f , it immediately follows from the fact that
we perform a constant number of link, cut, and CMV query operations, hence we only need
to argue about correctness.
Notice that after we cut edge e from Υv in step (i), the tree T 0 of Υv containing c has
exactly one (distinct) marked vertex u for each edge (u, v) ∈ S(e, v). The claim follows
as, by construction, the distance from c to u in T 0 is dT 0 (c, u) = dT 0 (c, u) + dT 0 (u, u) =
dT (c, u) + w(f ).
J

C

Dynamic maintenance of the upper envelopes

Procedure FindCriticalCandidate needs the auxiliary structure Qe . Explicitly building
such a structure for each edge e would be too expensive. In the remaining of this section we
show how all the Qe ’s can be built in O(m log4 n) time and O(m log2 n) space. The idea is
to exploit the order in which failing edges are considered, so as to reuse previously computed
information to build Qe .
We implement Qe as a dictionary that allows us to add, delete, and search for elements
in O(log n) time per operation. Each element of Qe is a data structure that can store a
set F of linear functions and is able (i) to dynamically add/remove a function to/from F
in O(log |F|) time, (ii) given t ∈ R, to report a function in UEF (t) in O(log |F|) amortized
time [8].

D. Bilò et al.

Each data structure in the dictionary is associated with a pair Ψ, Λ of trees of T and will
contain all the functions Φb,c,g where b and c are the parent centroids of Ψ and Λ, respectively,
e
and g ∈ S(e, V (Ψ) ∩ Ue , V (Λ) ∩ De ). We name such a structure H(Ψ,Λ)
. The pair (Ψ, Λ) is
e
also the key of H(Ψ,Λ) in the dictionary.
Observe now that we can answer the query Qe (f, Ψ, Λ) (used in FindCriticalCandidate)
e
in O(log n) amortized time, as follows: we search for HΨ,Λ
∈ Qe in O(log n) time, and then
e
we perform a query operation on HΨ,Λ with t = tb,c (f ) where b and c are the parent centroids
of Ψ and Λ, respectively (see Lemma 11).
We now show how to build and maintain the Qe ’s. Remember that we process the edges
e ∈ E(T ) in a bottom-up fashion. Let Te be the subtree of T induced by De . Whenever Te
consists of a single vertex, we build Qe from scratch. If Te contains 2 or more vertices then
there are at most two edges e1 , e2 ∈ E(Te ) that are incident to e. We build Qe by merging
Qe1 and Qe2 . This merge operation consists of a join step followed by an update step.
e
Whenever we add a function Φb,c,g to a structure H(Ψ,Λ)
of Qe and we are either performing
the update step or we are building Qe from scratch, we say that we insert Φb,c,g into Qe .
We associate a non-negative integer νe to Qe that we call virtual size of Qe . The virtual size
of Qe is the overall number of inserts that have been performed either on Qe itself or on any
e0
other H(Ψ,Λ)
such that e0 is an edge of Te .

C.1

Building Qe from scratch

We start by creating an empty dictionary Qe (initially νe = 0). Since we are building Qe
from scratch, Te contains only one vertex, say y. For each edge g = (x, y) ∈ S(e, Ue , y), we
explicitly consider all the pairs of trees (Ψ, Λ), such that Ψ contains x and Λ contains y, and
e
we let b and c be the parent centroids of Ψ and Λ, respectively. We look for H(Ψ,Λ)
in the
e
e
e
dictionary of Qe , if H(Ψ,Λ) already exists, we add Φb,c,g to H(Ψ,Λ) . If H(Ψ,Λ) is not found,
e
e
e
we create a new empty structure H(Ψ,Λ)
, we add Φb,c,g into H(Ψ,Λ)
, and we add H(Ψ,Λ)
to
Qe . In both cases we have that Φb,c,g is inserted into Qe and hence we increase νe by 1.

C.2

Building Qe by merging

Let e = (p, q) and remember that Te contains more than 1 vertex. Since q has degree at
most 3 in T , there are either 1 or 2 edges in Te that are incident to q. Here we will discuss
the case in which those edges are exactly 2 (as the case in which q is incident to only one
edge is simpler).
Let e1 , e2 be the two edges incident to q in Te . We will merge Qe1 and Qe2 in order to
obtain Qe . This operation is destructive, i.e., Qe1 and Qe2 will no longer exist at the end
of the merge operation. Notice, however, that since we are processing the edges of T in a
bottom-up fashion, Qe1 and Qe2 will no longer be needed by the algorithm.
The merge operation consists of two steps: the join step and the update step.

C.2.1

The join step

W.l.o.g., let νe1 ≥ νe2 . We start by renaming Qe1 to Qe (so that all the structures that
e1
e
belong to the dictionary of Qe1 that were named H(Ψ,Λ)
are now named H(Ψ,Λ)
).
e2
e
Now, for each structure H(Ψ,Λ) in Qe2 , we first search for the structure H(Ψ,Λ) in Qe and,
e
if such a structure is not found, we add new empty structure H(Ψ,Λ)
to Qe . Then, we move
e2
e2
e
each function Φb,c,g in H(Ψ,Λ) to H(Ψ,Λ) , i.e., we remove Φb,c,g from H(Ψ,Λ)
and, if Φb,c,g is
e2
e
e
not in H(Ψ,Λ) , we add it to H(Ψ,Λ) . Finally, after all the structures H(Ψ,Λ) in Qe2 have been
considered, we destroy Qe2 and we set νe to νe1 + νe2 .

XX:15

XX:16

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

C.2.2

The update step

After the merge step is completed, Qe contains all the functions corresponding to the edges
g in S(e1 ) ∪ S(e2 ).
Notice, however, that all the edges (x, y) such that the lowest common ancestor (LCA)
of x and y in T is q are both in S(e1 ) and S(e2 ) but they do not belong to S(e), and hence
they should not appear in Qe . On the converse, the edges in S(e, Ue , q) are neither in S(e1 )
nor in S(e2 ) but they belong to S(e), hence their corresponding functions should be added
to Qe . This is exactly the goal of the update step.
We start by deleting the extra functions from Qe . We iterate over each edge g = (x, y)
such that the LCA of x and y is q and, for each pair of trees (Ψ, Λ) such that Ψ contains x
e
and Λ contains y, we delete Φb,c,g from H(Ψ,Λ)
where b and c are the parent centroids of Ψ
e
e
and Λ respectively. If H(Ψ,Λ) becomes empty, we also delete H(Ψ,Λ)
from Qe .
We now add the missing functions to Qe . For each g = (x, q) ∈ S(e, Ue , q), and for each
e
pair of trees (Ψ, Λ), such that Ψ contains x and Λ contains q, we first search for H(Ψ,Λ)
in
e
Qe and, if it does not exist, we add new empty structure H(Ψ,Λ) to Qe . Then, we add Φb,c,g
e
to H(Ψ,Λ)
, where b and c are the parent centroids of Ψ and Λ respectively. We increase νe by
1 to account for this insertion.

C.3

Analysis

Here we bound the time required to dynamically maintain all the upper envelope structures.
I Lemma 18. The overall number of distinct functions Φb,c,g ever inserted into at least one
of the structures Qe is O(m log2 n).
Proof. Let us consider any edge g = (x, y) ∈ E(G) \ E(T ). If a function Φb,c,g associated
e
with g is inserted into any Qe , this means that it added to some H(Ψ,Λ)
such that x ∈ V (Ψ),
y ∈ V (Λ), and b (resp. c) is the parent centroids of Ψ (resp. Λ). Notice that there are
O(log n) trees τ of the centroid decomposition T that contain x (resp. y), meaning that
there are O(log2 n) functions Φb,c,g associated to g. The claim follows by summing over all
the edges in E(G) \ E(T ).
J
I Lemma 19. Each function Φb,c,g contributes at most 2 to the virtual size νe of any Qe .
Proof. It suffices to bound the overall number of insertions of Φb,c,g (regardless of the
structure Qe into which Φb,c,g is inserted). To this aim, consider the edge g = (x, y)
associated with Φb,c,g and, w.l.o.g., let x be the vertex that is closest to the root of T . Let
also ex (resp. ey ) be the edge from the parent of x to x (resp. from the parent of y to y) in
T . We distinguish two cases depending on the relative positions of x and y in T . If x is an
ancestor of y, then Φb,c,g is only inserted in Qey . Indeed, g belongs to S(ey ) but it does not
belong to any S(e0 ) where e0 ∈ E(Tey ) is incident to ey in Tey . For any other pair of edges
e00 , e000 ∈ E(T ) such that e000 is incident to e00 in Te00 we have that either g does not belong to
S(e00 ), or it belongs to both S(e00 ) and S(e000 ), and hence Φb,c,g is not added to Qe00 . If x is
not an ancestor of y, then a similar argument shows that Φb,c,g can only be inserted in Qex
and in Qey . The claim follows.
J
I Lemma 20. Each function Φb,c,g is moved O(log n) times.
Proof. When a function is moved from any Qe2 to Qe it is because we are merging Qe1
with Qe2 , where e1 and e2 are edges incident to e in Te . Notice that, before the merge
operation takes place, we must have νe1 ≥ νe2 and hence, at the end of the merge operation,

D. Bilò et al.

νe ≥ νe1 + νe2 ≥ 2νe2 . In other words, each time a function Φb,c,g is moved, we have that
the virtual size of the structure to which Φb,c,g belongs at least doubles. Therefore, after a
function has been moved r times, the structure containing Φb,c,g must have a virtual size of
at least 2r .
Notice now that Lemma 18 and Lemma 19 imply an upper bound of O(m log2 n) to the
virtual size of any Qe . We can conclude that a function can be moved O(log(m log2 n)) =
O(log n) times.
J
I Proposition 2. The total time spent building and merging all the data structures Qe is
O(m log4 n).
Proof. From Lemma 18 and Lemma 19 we have that the total number of insertions of
e
functions Φb,c,g into the structures H(Ψ,Λ)
is O(m log2 n) and, since each insertion requires
time O(log n), the total time spent due to insertions is O(m log3 n). Moreover, since each
function is deleted at most once, and a deletion takes O(log n) time, we have that the total
time spent for deleting functions is O(m log3 n).
Concerning moving of functions, by Lemma 20 we have that every function is moved
O(log n) times. Since there are O(m log2 n) functions, as shown by Lemma 18, and a function
can be moved in O(log n) time, we have that the total time spent moving functions is
O(m log4 n).
J

XX:17

