Tree spanners of bounded degree graphs
Ioannis Papoutsakis
Kastelli Pediados, Heraklion, Crete, Greece, 700 06

arXiv:1503.06822v5 [cs.DM] 9 May 2016

October 19, 2017
Abstract
A tree t-spanner of a graph G is a spanning tree of G such that the distance between pairs of
vertices in the tree is at most t times their distance in G. Deciding tree t-spanner admissible graphs
has been proved to be tractable for t < 3 and NP-complete for t > 3, while the complexity status of
this problem is unresolved when t = 3. For every t > 2 and b > 0, an efficient dynamic programming
algorithm to decide tree t-spanner admissibility of graphs with vertex degrees less than b is presented.
Only for t = 3, the algorithm remains efficient, when graphs G with degrees less than b log |V (G)| are
examined.
Keywords: Tree spanner, Distance, Spanning tree, Efficient graph algorithm, Bounded degree graph.

1

Introduction

A t-spanner of a graph G is a spanning subgraph of G, such that the distance between pairs of vertices in
the t-spanner is at most t times their distance in G. Spanners, when they have a few edges, approximate
the distances in the graph, while they are sparse. Spanners of a graph that are trees attain the minimum
number of edges a spanner of the graph can have. There are applications of spanners in a variety of areas,
such as distributed computing [2, 28], communication networks [26, 27], motion planning and robotics
[1, 9], phylogenetic analysis [3] and in embedding finite metric spaces in graphs approximately [30]. In
[29] it is mentioned that spanners have applications in approximation algorithms for geometric spaces
[19], various approximation algorithms [12] and solving diagonally dominant linear systems [31].
On one hand, in [4, 8, 7] an efficient algorithm to decide tree 2-spanner admissible graphs is presented,
where a method to construct all the tree 2-spanners of a graph is also given. On the other hand, in [8, 7]
it is proven that for each t ≥ 4 the problem to decide graphs that admit a tree t-spanner is an NPcomplete problem. The complexity status of the tree 3-spanner problem is unresolved. In [13], for
every t, an efficient algorithm to determine whether a planar graph with bounded face length admits a
tree t-spanner is presented. In [14] the existence of an efficient (actually linear) algorithm for the tree
spanner problem on bounded degree graphs is shown, using a theorem of Logic; while it is mentioned
that: “It would be interesting to show that one could use tools that do not rely on Courcelles theorem
or Bodlaenders algorithm to speed up practical implementations”. In this article, for every t, an efficient
dynamic programming algorithm to decide tree t-spanner admissibility of bounded degree graphs is
presented (theorem 1).
Tree t-spanners (t ≥ 3) have been studied for various families of graphs. If a connected graph is a
cograph or a split graph or the complement of a bipartite graph, then it admits a tree 3-spanner [7].
Also, all convex bipartite graphs have a tree 3-spanner, which can be constructed in linear time [32].
Efficient algorithms to recognize graphs that admit a tree 3-spanner have been developed for interval,
permutation and regular bipartite graphs [17], planar graphs [13], directed path graphs [16], very strongly
chordal graphs, 1-split graphs and chordal graphs of diameter at most 2 [6]. In [23] an efficient algorithm
to decide if a graph admits a tree 3-spanner of diameter at most 5 is presented. Moreover, every strongly
chordal graph admits a tree 4-spanner, which can be constructed in linear time [5]; note that, for each t,
there is a connected chordal graph that does not admit any tree t-spanner. The tree t-spanner problem
has been studied for small diameter chordal graphs [6], diametrically uniform graphs [18], and outerplanar
graphs [20]. Approximation algorithms for the tree t-spanner problem are presented in [11, 27], where
in [11] a new necessary condition for a graph to have a tree t-spanner in terms of decomposition is also
presented.
1

There are NP-completeness results for the tree t-spanner problem for families of graphs. In [13], it is
shown that it is NP-hard to determine the minimum t for which a planar graph admits a tree t-spanner.
In [10], it is proved that, for every t ≥ 4, the problem of finding a tree t-spanner is NP-complete on
K6 -minor-free graphs. For any t ≥ 4, the tree t-spanner problem is NP-complete on chordal graphs of
diameter at most t + 1, when t is even, and of diameter at most t + 2, when t is odd [6]; note that
this refers to the diameter of the graph not to the diameter of the spanner. In [24] it is shown that the
problem to determine whether a graph admits a tree t-spanner of diameter at most t + 1 is tractable,
when t ≤ 3, while it is an NP-complete problem, when t ≥ 4. This last result is used in [25] to hint at
the difficulty to approximate the minimum t for which a graph admits a tree t-spanner.
The tree 3-spanner problem is very interesting, since its complexity status is unresolved. In [22] it is
shown that only for t = 3 the union of any two tree t-spanners of any given graph may contain big induced
cycles but never an odd induced cycle (other than a triangle); such unions are proved to be perfect graphs.
The algorithm presented in this article is efficient only for t ≤ 3, when graphs with maximum degree
O(log n) are considered, where n(G) is the number of vertices of each graph G (section 5). The tree
3-spanner problem can be formulated as an integer programming optimization problem. Constraints for
such a formulation appear in [22], providing certificates of tree 3-spanner inadmissibility for some graphs.

2

Definitions

In general, terminology of [33] is used. If G is a graph, then V (G) is its vertex set and E(G) its edge set.
An edge between vertices u, v ∈ G is denoted as uv. Also, G \ {uv} is the graph that remains when edge
uv is removed from G. Let v be a vertex of G, then NG (v) is the set of G neighbors of v, while NG [v] is
NG (v) ∪ {v}; in this article, graphs do not have loop edges. The degree of a vertex v in G is the number
of edges of G incident to v. Here, ∆(G) is the maximum degree over the vertices of G.
Let G and H be two graphs. Then, G \ H is graph G without the vertices of H, i.e. V (G \ H) =
V (G) \ V (H) and E(G \ H) = {uv ∈ E(G) : u 6∈ V (H) and v 6∈ V (H)}. The union of G and H, denoted
as G ∪ H, is the graph with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H). Similarly, the intersection
of G and H, denoted as G ∩ H, is the graph with vertex set V (G) ∩ V (H) and edge set E(G) ∩ E(H).
Additionally, G[H] is the subgraph of G induced by the vertices of H, i.e. G[H] contains all vertices in
V (G) ∩ V (H) and all the edges of G between vertices in V (G) ∩ V (H). Note that the usual definition of
induced subgraph refers to H being a subgraph of G.
The G distance between two vertices u, v ∈ G is the length of a u, v shortest path in G, while it is
infinity, when u and v are not connected in G. The definition of a tree t-spanner follows.
Definition 1 A graph T is a t-spanner of a graph G if and only if T is a subgraph of G and, for every
pair u and v of vertices of G, if u and v are at distance d from each other in G, then u and v are at
distance at most t · d from each other in T . If T is also a tree, then T is a tree t-spanner of G.
Note that in order to check that a spanning tree of a graph G is a tree t-spanner of G, it suffices to
examine pairs of vertices that are adjacent in G [7]. There is an additive version of a spanner as well
[15, 29], which is not studied in this article. In the algorithm and in the proofs, r-centers are frequently
used.
Definition 2 Let r be an integer. Vertex v of a graph G is an r-center of G if and only if for all vertices
u in G, the distance from v to u in G is less than or equal to r.
To refer to all the vertices near a central vertex, the notion of a sphere is used.
Definition 3 Let r be an integer and v a vertex of a graph G. Then, the subgraph of G induced by the
vertices of G at distance less than or equal to r from v is the sphere of G with center v and radius r; it
is denoted as (v, r)G -sphere.
Obviously, v is an r-center of a graph G, if and only if the (v, r)G -sphere is equal to G.
Let f, g be functions from the set of all graphs to the non negative integers. Then, f is O(g) if and
only if there are graph G0 and integer M such that f (G) ≤ M g(G) for every G with |V (G)| > |V (G0 )|.
An algorithm that runs in polynomial time is called efficient.

2

Algorithm Find Tree spanner(G, t)
Input: A connected nonempty graph G and an integer t > 1.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

A0G = ∅
For (k = 1 to |V (G)|) {
AkG = ∅
For (vertex v ∈ G) {
Sv = {S ⊆ G : S is a tree t-spanner of G[S] and v is a b 2t c-center of S}
For (S ∈ Sv ) {
k
Tv,S
= Find Subtree(G, t, v, S, k,Ak−1
G )
k
k
AG = AkG ∪ {Tv,S
}
k
k
If (V (G) = V (Tv,S
)) Return(Tv,S
)}}
k−1
Discard AG }
Return(G does not admit a tree t-spanner.)

Table 1: Algorithm Find Tree spanner(G, t). Procedure Find Subtree is described in table 2.

3

Description of the algorithm.

In [21], a characterization of tree t-spanner admissible graphs in terms of decomposition states, generally
speaking, that if a tree t-spanner admissible graph G does not have small diameter then it is the union
of two tree t-spanner admissible graphs whose intersection is a small diameter subgraph of G (this result
requires further definitions to be stated exactly and it is not used in the proofs of this article). So, it
may be the case that, starting with small diameter subgraphs and adding on them partial solutions of
the remaining graph, a tree t-spanner of the whole graph is built.
Algorithm Find Tree spanner in table 1 has as input a graph G and an integer t > 1. Its output is a
tree t-spanner of G or a message that G does not admit any tree t-spanner. Being a dynamic programming
algorithm, it grows partial solutions into final solutions starting from small subtrees of G. Obviously,
each such subtree must be a tree t-spanner of the subgraph of G induced by the vertices of the subtree.
All these subtrees are the first partial solutions of the dynamic programming method and are generated
by exhaustive search (first stage of the algorithm). Graphs of bounded degree have vertices of bounded
neighborhoods; therefore, this search for small subtrees is no harm. Note that the algorithm works for
all input graphs but its efficiency suffers when graphs of big degrees are examined.
In each of the next stages of this dynamic programming algorithm, each partial solution is examined
and, then, if possible, it is incremented (procedure Find Subtree in table 2). The initial subtree of each
k
partial solution (which was formed in the first stage) is its core. Let Tv,S
be a partial solution that
k
is being examined. Removing the core of Tv,S , which is S, from G creates some components. Each
k
k
such component Q that is not covered so far by Tv,S
is considered. The core of Tv,S
is put together
with an appropriate (based on Q) portion of nearby partial solutions; if the resulting graph is a tree
t-spanner of the subgraph of G induced by the vertices of the resulting graph, then the partial solution
k
k
under examination Tv,S
is incremented by the resulting graph. This increment helps Tv,S
to cover Q.
If G admits a tree t-spanner, then some of the partial solutions eventually cover G; if so, the algorithm
outputs one of them (line 9 of table 1). Otherwise, |V (G)| stages suffice to conclude that G does not
admit any tree t-spanner (line 11 of table 1). The description of the algorithm in the two tables has some
details, which are explained in the following paragraphs.
Let us start with table 1. Here, A0G is set to ∅ (line 1) and its only use is to call a procedure later
on correctly. To give motion to the process of growing partial solutions a main For loop is used (line 2),
where variable k is incremented by 1 at the end of each stage, starting from 1. Set AkG is to store the
progress on partial solutions and it is initialized to ∅ (line 3); i.e. it is a set whose elements are subtrees
of G. The first stage (k=1) is different from the rest in not having previous partial solutions to merge.
First, it is necessary to pick names for the primary partial solutions. For each vertex v of G a set Sv is
formed (line 5). Each subgraph S of G that is a tree t-spanner of G[S] and has v as a b 2t c-center becomes
an element of Sv . This set Sv can be formed by exhaustively checking all the subtrees of the sphere of G
with center v and radius b 2t c (see lemma 6). Note that the computations to form Sv can be done only for
3

Procedure Find Subtree(G, t, v, S, k, Ak−1
G )
Input: A graph G, an integer t > 1, a vertex v ∈ G, a tree t-spanner S of G[S]
with b 2t c-center v, an integer k ≥ 1, and a set Ak−1
of subtrees of G.
G
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

If (k = 1) {
Qv,S = {Q ⊆ G : Q is a component of G \ S}
// static
Return(S)}
else {
k−1
k−1
k
Tv,S
= Tv,S
// Tv,S
is in Ak−1
G
For (component Q ∈ Qv,S ) {
k−1
For (Tu,R
∈ Ak−1
such that u ∈ NS (v)) {
G
k−1
k
Tv,S,u,R,Q = (Tu,R [Q ∪ R] ∪ S) \ ((R \ S) \ Q)
k
If (Tv,S,u,R,Q
is a tree t-spanner of G[Q ∪ S]) {
k
k
k
Tv,S
= Tv,S
∪ Tv,S,u,R,Q
Qv,S = Qv,S \ {Q}
Break}}}
// Stop search in Ak−1
G
k
Return(Tv,S )}

Table 2: Procedure Find Subtree(G, t, v, S, k, Ak−1
G ). In line 13, variable Qv,S has been declared as
static; i.e. it is stored locally for later use, when the procedure is called again.

1
. Second, each
k = 1. Then, for each member S of Sv a partial solution is considered under the name Tv,S
primary partial solution must be initialized (line 7). This is a job for procedure Find Subtree, which for
1
= S. Of course, each newly formed primary partial solution is stored in A1G
k = 1 returns S; i.e. Tv,S
(line 8). It may well be the case, when G is a small graph, that some of these primary solutions already
1
spans G (i.e. V (G) = V (Tv,S
)); then, a tree t-spanner of G is found. This completes the first stage of
the main For loop.
For k > 1, partial solutions are merged if possible. Again, all partial solutions are considered one by
one. Procedure Find Subtree in table 2 receives as input (among others) vertex v and subtree S ∈ Sv ;
k
, where k is just the number
these two determine the name of the partial solution under examination Tv,S
of the stage the algorithm is in. It also receives as input all the partial solutions formed in the previous
stage of the dynamic programming method through set Ak−1
G . Procedure Find Subtree has saved locally
the set of components Qv,S of G \ S, when it was called during the first stage of the main algorithm
(k = 1). Set Qv,S is a static variable; the content of this set changes and these changes are remembered
when the procedure is called again. Another way to put it is that Qv,S is a global variable, which is not
lost each time the procedure ends.
The central set of operations of this dynamic programming algorithm is in procedure Find Subtree,
k
when k > 1 (table 2, lines 15 to 24) . First, partial solution Tv,S
takes the value that it had in the
k−1
k−1
k
previous stage, which had been stored in AG ; i.e Tv,S = Tv,S (line 16). Then, second, each component
k
Q in Qv,S is examined to check if Tv,S
can be extended towards Q (line 17). Third, this extension will
k−1
be done using other nearby partial solutions in Ak−1
that involve
G . For this, all partial solutions in AG
as central vertex a neighbor of v in S are considered, one at a time (line 18); the central vertex of partial
k−1
solution Tu,R
is u.
k−1
Fourth, assume that the nearby partial solution Tu,R
is considered when component Q is examined.
k
Then, in line 19, an auxiliary graph Tv,S,u,R,Q is formed (see figure 1). The fundamental part of this
k−1
auxiliary graph is Tu,R
[Q ∪ R]; i.e. the restriction of the considered nearby partial solution to the
component under examination (plus its core R). The intuition behind this operation is that u may
k−1
be “closer” than v to Q and, therefore, Tu,R
may have covered Q in a previous stage of the dynamic
programming method. For example, for k = 2, input graph G may “end” towards the “direction” of
k−1
1
edge vu; i.e. V (Q) ⊆ V (R) and, therefore, Tu,R
covers Q. In most of the cases Tu,R
does not contain
k−1
all the vertices of Q; then, Tu,R [Q ∪ R] is still meaningful, because of the slightly different than the
usual definition of induced subgraph used in this article (see section 2). Having the foundation in hand,
k−1
i.e. graph Tu,R
[Q ∪ R], subtree S is added to it; lets call for convenience the resulting graph B (i.e.

4

v

S

u

R

Q

k
Figure 1: The formation of auxiliary graph Tv,S,u,R,Q
in procedure Find Subtree of table 2. The left circle is
S, which is a tree t-spanner of G[S] and has v as a b 2t c-center. Similarly, the right circle is R, which is a tree
t-spanner of G[R] and has u as a b 2t c-center; here, u is a neighbor of v in S. Also, Q is a component of G \ S. The
k−1
gray area is (R \ S) \ Q. The vertices that correspond to this gray area are removed from B = Tu,R
[Q ∪ R] ∪ S
to form the auxiliary graph.

k−1
B = Tu,R
[Q ∪ R] ∪ S; here, B is not used as a variable within table 2). Note that B may not even be a
k
tree, because S ∪ R may contain a cycle. Since partial solution Tv,S
is to be incremented towards exactly
1
k
Q, graph (R \ S) \ Q (gray area in figure 1) is removed from B to form the auxiliary graph Tv,S,u,R,Q
(see lemma 4).
k
is a tree t-spanner of G[Q ∪ S], then it is added to the partial
Fifth, if auxiliary graph Tv,S,u,R,Q
k
k
k
(line 21). The result is again a tree t-spanner
∪ Tv,S,u,R,Q
solution under examination; i.e. Tv,S = Tv,S
of the subgraph of G induced by the vertices of the result (see lemma 3 and lemma 2). Also, in this
case, component Q is removed from Qv,S (line 22) and the search for nearby partial solutions to grow
k
k
Tv,S
towards Q stops (line 23), since Tv,S
now covers Q. The execution continues after the If statement
k
can be discarded at this
(line 20) with the next component in Qv,S . Note that auxiliary graph Tv,S,u,R,Q
point. These five steps complete the central set of operations of this dynamic programming algorithm.
k
Of course, after all components in Qv,S have been examined, procedure Find Subtree returns Tv,S
to
the main program (line 24).
A few comments on the algorithm follow. The algorithm works for t = 2 as well, although there is an
efficient algorithm for this case [4, 8, 7]. Maintaining the various sets used in the algorithm is done using
linked lists. This way a For loop on elements of a set retrieves sequentially all elements in a linked list.
Finally, procedure Find Subtree doesn’t need to check if its input is appropriate.

4

Proof of correctness

The following lemma is employed in various places within this section; when it is used in a proof, a footnote
gives the correspondence between the variable names in the proof and the names in its statement below.
It describes a basic property of spanners: vertices too far apart in a spanner of a graph cannot be adjacent
in the graph. The notion of a sphere has been defined in section 2
Lemma 1 Let G be a graph, T a tree t-spanner of G, and x a vertex of G, where t > 1. Let X be the
(x, b 2t c)T -sphere. Let y be a T neighbor of x and let Ty be the component of T \ {xy} that contains y.
Then, there is no edge of G from a vertex in Ty \ X to a vertex in (G \ Ty ) \ X.
Proof. Assume, towards a contradiction, that there is an edge of G between a vertex p ∈ Ty \ X and a
vertex q ∈ (G \ Ty ) \ X. Let P1 be the T path from p to x. Then, all the vertices of P1 but x are vertices
of Ty . Also, the length of P1 is strictly greater than b 2t c, because X contains all the vertices of T at T
distance less than or equal to b 2t c from x and p is out of X. Let P2 be the T path from q to x. Then,
none of the vertices of P2 is a vertex of Ty , because q 6∈ Ty and x 6∈ Ty . Also, the length of P2 is strictly
greater than b 2t c, because X contains all the vertices of T at T distance less than or equal to b 2t c from
x and q is out of X. Then, the T path from p to q has length greater than or equal to 2b 2t c + 2; i.e. the
T distance between the endpoints of edge pq of G is strictly greater than t. This is a contradiction to T
being a tree t-spanner of G.
2
1 Due to the exhaustive search for primary partial solutions, there is always some R0 that will do the job instead of R,
such that (R0 \ S) \ Q = ∅. But removing the gray area facilitates the proof of correctness; this way more nearby partial
solutions may help the partial solution under examination to grow.

5

k
When growing a partial solution T1 = Tv,S
towards a component Q of G \ S, by adding an auxiliary
k
graph T2 = Tv,S,u,R,Q (line 21 of table 2), the result T1 ∪ T2 must be a tree t-spanner of G[T1 ∪ T2 ]; the
following lemma handles that. The vertices of forest T2 \ T1 are the vertices of Q, while the vertices of
forest T1 \ T2 are the vertices of the components of G \ S that have already been covered by T1 ; since
these two forests correspond to such components, there is no edge of the input graph between them. The
intersection T1 ∩ T2 corresponds to the core (the initial value) of partial solution T1 , which is S.

Lemma 2 Let G be a graph. Assume that T1 is a tree t-spanner of G[T1 ] and that T2 is a tree t-spanner
of G[T2 ]. Also, assume that there is no edge of G between a vertex in T1 \ T2 and a vertex in T2 \ T1 . If
T1 ∩ T2 is a nonempty tree, then T1 ∪ T2 is a tree t-spanner of G[T1 ∪ T2 ].
Proof. Let T∪ = T1 ∪ T2 and T∩ = T1 ∩ T2 . First, it is proved that T∪ is a tree. Let Q be the
components of T∪ \ T∩ . Trivially, each component in Q is either an induced subgraph of T1 \ T2 or an
induced subgraph of T2 \ T1 .
Consider a component Q in Q. Obviously, T∪ is a connected graph (T∩ is nonempty). So, there must
be at least one edge of T∪ between Q and T∩ . Without loss of generality, assume that Q is an induced
subgraph of T1 \ T2 . So, all the edges of T∪ between Q and T∩ belong to T1 . Therefore, since Q and T∩
are connected subgraphs of T1 and T1 is a tree, there is exactly one edge of T∪ between Q and T∩ .
Here, T∩ is an induced subgraph of T∪ , because any extra edge would form a cycle in T1 or in T2 . So,
T∪ is a connected graph that consists of |Q| + 1 vertex disjoint trees plus |Q| edges; therefore, it is a tree.
Second, it is proved that T∪ is a t-spanner of G[T1 ∪ T2 ]. Consider an edge vu of G[T1 ∪ T2 ]. Then,
vu is an edge of G[T1 ] or an edge of G[T2 ], because there is no edge of G between a vertex in T1 \ T2 and
a vertex in T2 \ T1 . Assume, without loss of generality, that vu is an edge of G[T1 ]. Since T1 is a tree
t-spanner of G[T1 ], the distance in T∪ between v and u is at most t.
2
Incrementing of partial solutions is done through a specific command within the algorithm. The
following lemma examines one by one the executions of this command and confirms that the incrementing
is done properly. For this, a double induction is used.
Lemma 3 Let G be a graph and t > 1 an integer. For every v ∈ G, for every S ∈ Sv and for every k
k
k
k
are constructed in algorithm
], where Sv and Tv,S
is a tree t-spanner of G[Tv,S
(1 ≤ k ≤ |V (G)|), Tv,S
Find Tree spanner of table 1 on input (G, t).
1
belongs to A1G and it is equal to S, which is a tree t-spanner of G[S]; so,
Proof. Since S ∈ Sv , Tv,S
k
is incremented through command
the lemma holds for k = 1. Let lk be the total number of times Tv,S
k
k
k
Tv,S
= Tv,S
∪ Tv,S,u,R,Q

(1)

k,l
k
k
in line 21 of table 2. Denote with Tv,S
the value of variable Tv,S
, when Tv,S
has been incremented l
k−1,l

2,0
k,0
1
times, through command (1) above, where 2 ≤ k ≤ |V (G)|. Then, Tv,S
= Tv,S
and Tv,S
= Tv,S k−1 ,
k,l
k,l−1
k
where 3 ≤ k ≤ |V (G)| (line 16 of table 2). Also, Tv,S = Tv,S ∪ Tv,S,u,R,Q
, where 2 ≤ k ≤ |V (G)| and
1 ≤ l ≤ lk .
k,0
First, it is proved, by induction on l, that for each k (2 ≤ k ≤ |V (G)|) if Tv,S
is a tree t-spanner of
k,0
k,l
k,l
G[Tv,S
], then Tv,S
is a tree t-spanner of G[Tv,S
], where 0 ≤ l ≤ lk . The base case (l = 0) holds trivially.
k,l−1
k
For the induction step (1 ≤ l ≤ lk ), T1 = Tv,S
is incremented by T2 = Tv,S,u,R,Q
for some u, R and
k,l
k,l
Q to become Tv,S ; i.e. Tv,S = T1 ∪ T2 . Then, T2 must be a tree t-spanner of G[Q ∪ S] (see condition of
If statement in line 20 of table 2). Also, T1 is a tree t-spanner of G[T1 ], by induction hypothesis. The
vertex set of T2 is V (S ∪ Q). Also, the vertex set of T1 is the vertices of S union the vertices of some
components of G \ S other than Q, because Q has not been used to increment this partial solution before.
So, there is no edge of G between a vertex in T1 \ T2 and a vertex in T2 \ T1 and V (T1 ∩ T2 ) = V (S). By
1
construction of T2 , S is a subtree of T2 . Also, T1 contains S, because T1 contains Tv,S
, which is equal to
k,l
k,l
S. So, T1 ∩ T2 is S, which is a nonempty tree. Here, Tv,S = T1 ∪ T2 . Therefore, by lemma 2, Tv,S
is a
k,l
tree t-spanner of G[Tv,S ].
k,l
Second, the lemma is proved by induction on k; i.e. it is proved that Tv,S
is a tree t-spanner of
k,l
2,0
1
G[Tv,S ], where 2 ≤ k ≤ |V (G)| and 0 ≤ l ≤ lk . For the base case, Tv,S is equal to Tv,S
, which has been

6

2,l
2,l
1
shown to be a tree t-spanner G[Tv,S
]. So, by the first induction, Tv,S
is a tree t-spanner of G[Tv,S
], for
k−1,lk−1

k,0
0 ≤ l ≤ lk . For the induction step, Tv,S
is equal to Tv,S

t-spanner

k−1,l
G[Tv,S k−1 ].

So, by the first induction,

k,l
Tv,S

, which, by induction hypothesis, is a tree

k,l
is a tree t-spanner of G[Tv,S
], for 0 ≤ l ≤ lk .

2

k
Assume that a partial solution Tv,S
is about to grow towards a component W of G \ S with the help
k−1
0
of a nearby partial solution T = Tu,R . Then, the vertices of R that are not in S nor in W are not needed
k
to grow Tv,S
. The following lemma facilitates this process.

Lemma 4 Let G be a graph and T a tree t-spanner of G, where t > 1. Let v be a vertex of G and let S be
the (v, b 2t c)T -sphere. Let u be a T neighbor of v and let R be the (u, b 2t c)T -sphere. Let W be a component
of G \ S. Let T 0 be a tree t-spanner of G[T 0 ], such that R ⊆ T 0 . Let L be (R \ S) \ W . If T 0 [W ∪ R] ∪ S
is a tree t-spanner of G[W ∪ S ∪ R], then (T 0 [W ∪ R] ∪ S) \ L is a tree t-spanner of G[W ∪ S].
Proof. Obviously, L corresponds to the gray area in figure 1. Let g be a vertex in L. Then, g 6∈ S
and g 6∈ W . So, if there is an edge of G from g to a vertex in W , then g must be in W , a contradiction.
Assume, towards a contradiction, that there is an edge e of T 0 [W ∪ R] ∪ S from g to a vertex in S ∪ R,
such that e 6∈ E(S ∪ R). Obviously, S ∪ R is a connected graph, because b 2t c > 0. Also, R ⊆ T 0 ; so, all
edges of S ∪ R are present in T 0 [W ∪ R] ∪ S. Therefore, there is a path in T 0 [W ∪ R] ∪ S between the
endpoints of e that avoids e (note that L ⊆ R). This is a contradiction to T 0 [W ∪ R] ∪ S being a tree.
So, since L does not contain any vertex of S, all edges of T 0 [W ∪ R] ∪ S incident to g must be edges of
R (it was proved earlier that there is no edge of G between g and a vertex in W ). Here, g must be at
distance exactly b 2t c from u, because g ∈ R \ S and S contains all the vertices at T distance less than or
equal to b 2t c − 1 from u. Therefore, g is incident to only one edge of T 0 [W ∪ R] ∪ S. So, removing L from
T 0 [W ∪ R] ∪ S results to a tree t-spanner of G[W ∪ S].
2
The main lemma in the proof of correctness of the algorithm follows. It guarantees that if the input
graph admits a tree t-spanner, then some partial solutions can grow during some stages of the algorithm.
To break its proof into small parts, minor conclusions appear as statements at the end of the paragraph
that justifies them and are numbered equation like. Also, intermediate conclusions appear as numbered
facts. The lemma is proved by induction on the number of stages of the algorithm (variable k in the main
For loop at table 1; see line 2). Note that the algorithm is ahead of the induction, in the sense that for
k = 2 the algorithm starts merging primary partial solutions, while the induction considers such merges
for k > b 2t c, as one can see in the proof of fact 3 (for t ≤ 3, though, the algorithm and the induction are
on the same page). The intuition behind the lemma is the following. If a graph admits a tree t-spanner
T , then there is a sphere S of T which is close to leaves of T , or to picture it, say that S is close to an
end of T . Then, a nearby sphere R does cover some of the leaves that S just misses. Here, S corresponds
k
that may
to the partial solution that may grow, while R corresponds to a nearby partial solution Tu,R
help it grow. This picture is described formally by fact 3, where H = ∅ means that S is close to an end
of T . After the first steps of the induction, some partial solutions have grown. Assume now that S is not
k
close to some end of T . Then, S is nearby to a partial solution Tu,R
, which is closer to that end of T
k
than S is. The induction hypothesis hints that, at some earlier stage, Tu,R
covered the part of the input
k
graph from R to that end of T . So, Tu,R
may help (see fact 4) the partial solution that corresponds to
S to grow.
Lemma 5 If G admits a tree t-spanner T (t > 1) for which there exists vector (k, v, S, W, u) such that:
1. 1 ≤ k ≤ |V (G)| − 1, v ∈ V (G),
2. S is the (v, b 2t c)T -sphere,
3. u is a T neighbor of v, Tu is the component of T \ {uv} that contains u,
4. W = {X ⊆ G : X is a component of G \ S and V (X) ⊆ V (Tu )}, and
5. v is a k-center of Tu ∪ S,
then algorithm Find Tree spanner on input (G, t) (see table 1) returns a graph or for every component
W ∈ W there exists RW ⊆ G such that:
k
• Tu,R
is stored in AkG of algorithm Find Tree spanner on input (G, t) and
W

7

k+1
k+1
k
• Tv,S,u,R
is a tree t-spanner of G[W ∪ S], where Tv,S,u,R
is the graph (Tu,R
[W ∪ RW ] ∪
W
W ,W
W ,W
S) \ ((RW \ S) \ W ) (see line 19 of table 2, where such auxiliary graphs are constructed).

Proof. Assume that algorithm Find Tree spanner on input (G, t) does not return a graph; then all
the stages of the main For loop of the algorithm are executed (line 2 of table 1). The lemma is proved
by induction on k. For the base case, k ≤ b 2t c. Here, S is the subtree of TSthat contains all the vertices
of T at T distance less than or equal to b 2t c from v. So, all the vertices in W have to be at T distance
strictly greater than b 2t c from
S v (each member of W is a component of G \ S). Here, v is a k-center of
Tu ∪ S; so, all vertices in W are at T distance less than or equal to k from v (the vertex set of each
component in W is subset of Tu ). So, W = ∅ and the lemma holds vacuously.

v
S

u

H
x=y

S

Wy

W

R

Figure 2: The situation for t = 3. Only edges of T are shown. The dashed line sets concern vertex sets involved
in the induction hypothesis. Note that, when t = 3, one can prove that for each y ∈ XW , sets Wy and Wy0
coincide.

For the induction step, b 2t c + 1 ≤ k ≤ |V (G)| − 1. Some definitions which are used throughout
the proof are introduced in this paragraph. Let W be a component in W. Let R be the (u, b 2t c)T sphere. Let XW = V (R ∩ W ). Let YW = {y ∈ NT (u) : there is a vertex x ∈ XW such that the T
path from x to u contains y}. Here, v is not in YW , because V (W ) ⊆ V (Tu ). Note that, when t ≤ 3,
XW = YW (figure 2). Now, for each y ∈ YW let Ty be the component of T \ {uy} that contains y.
To make use of induction hypothesis appropriate sets of components are defined. For each y ∈ YW let
Wy = {X ⊆ G : X is a component of G \ R and V (X) ⊆ V (Ty )}. Since a tree t-spanner for G[S ∪ W ]
is to be constructed, only the components of each Wy that fall within W are of interest.
So, for each
S
y ∈ YW , let Wy0 = {H ∈ Wy : H ⊆ W }. To refer to all these components, define H = y∈YW Wy0 .
A fundamental reason that the algorithm works is fact 1. It says that each component of G \ R falls
either nicely into W or completely out of W and, therefore, the induction hypothesis becomes useful (see
figure 4). On one hand, XW ⊆ V (W ), by definition of XW . Also, For every y ∈ YW , every component in
Wy0 is a subgraph of W . Therefore,
V(

[

H) ∪ XW ⊆ V (W )

(2)

On the other hand, let p be a vertex in W . Let P be the T path from p to v (see figure 3). Since
V (W ) ⊆ V (Tu ), P contains u and all its vertices but v belong to Tu . All the vertices of W are at T
distance strictly greater than b 2t c from v, by the definition of S (W is a component of G \ S). So, P
contains exactly one vertex, say vertex x, at T distance exactly b 2t c + 1 from v (P is a sub path of tree
T ). This means that x is at T distance exactly b 2t c from u. Therefore, x ∈ R (note that R contains all
the vertices at T distance less than or equal to b 2t c from u). Also, all the vertices of P from x to p are
at T distance strictly greater than b 2t c from v; so, there is a path in G \ S from p to x. But p ∈ W ; so,
x ∈ W as well. Then, x ∈ XW , because XW = V (R ∩ W ). So,
p ∈ XW , when p = x

(3)

When p 6= x, p is at T distance strictly greater than b 2t c from u, since x is at T distance exactly b 2t c
from u; so, p 6∈ R. Therefore, p is in a component, say component H1 , of G \ R (see figure 3). Assume,
towards a contradiction, that H1 6⊆ W . Here, H1 is a component of G \ R, W is a component of G \ S,
and H1 ∩ W 6= ∅. So, since H1 6⊆ W , there must be an edge e of G from a vertex in H1 ∩ W to a vertex
in S \ R. As it can be seen in figure 3, the T distance between the endpoints of e must be bigger than
8

t, which contradicts to T being a tree t-spanner of G; formally, lemma 1 is employed. Here, S \ R is a
subgraph of the component of T \{uv} that contains v (easily seen by the definitions of S and R); call that
component Tv . So, S \ R ⊆ Tv \ R. Also, V (W ) ⊆ V (Tu ) and H1 ⊆ G \ R; so, V (H1 ∩ W ) ⊆ V (Tu \ R).
But Tv ∩ Tu = ∅; so, H1 ∩ W ⊆ (G \ Tv ) \ R. Therefore, e is an edge of G from a vertex in Tv \ R to a
vertex in (G \ Tv ) \ R; this is a contradiction to lemma2 1. So,
H1 ⊆ W

(4)

Let y be the neighbor of u in P towards p (note that when t ≤ 3, x = y); then, y ∈ YW (since x ∈ P and
x ∈ XW ) and p ∈ Ty . Assume, towards a contradiction, that there is a vertex of H1 out of Ty . Then,
there must be an edge of H1 (and of G as well) from a vertex in Ty \ R to a vertex in (G \ Ty ) \ R, because
H1 is a component of G \ R. This is a contradiction to lemma3 1. So,
V (H1 ) ⊆ V (Ty )

(5)

Here, H1 is a component of G\R, such that V (H1 ) ⊆ V (Ty ) (statement (5)) and H1 ⊆ W (statement (4)).
So, H1 ∈ Wy0 . Therefore, since y ∈ YW , H1 ∈ Wy0 , and p ∈ H1 , it holds that:
[
p ∈ V ( H), when p 6= x

(6)

Since p is just any vertex in W , from statements (2), (3), and (6), the following holds.
S
Fact 1 V ( H) ∪ XW = V (W ).
y1

v u

x

y

p
H

P

y2
S

W
R

Figure 3: The shapes with fat lines correspond to S (left) and to W (right). The shapes with dashed lines
correspond to R (left) and to H (right; also, H may stand for H1 as well, depending on the context). All the
T neighbors of u are shown, namely, v, y1 , y, and y2 . The dark gray area is set XW . The subtrees of T that
correspond to TS
y and Ty2 are shown gray (including dark gray). Here, y1 is not in YW . The gray area out of R
S
S
corresponds to y∈YW ( Wy ), while the gray area out of R but within W corresponds to H. Here, P is a T
path from p to v; note that P contains only one vertex in the dark gray area, namely x. Finally, the hatched area
is S \ R.

Sphere R is going to be the required in the conclusion of the lemma RW . Note that, by removing the
gray area as shown in figure 1, sphere R is suitable for every component in W, not just W . Trivially, R
is a tree t-spanner of G[R], because it is a subtree of T . Also, u is a b 2t c-center of R, because u is defined
to be the center of sphere R of radius b 2t c. Therefore (line 5 of table 1), R ∈ Su and the following holds
(line 8 of table 1).
k
Fact 2 Algorithm Find Tree spanner on input (G, t) stores Tu,R
in AkG
k+1
Next, it is proved that Tv,S,u,R,W
is a tree t-spanner of G[W ∪ S]. For this, two cases are examined.
On one hand, consider the case that H = ∅. Then, an induction hypothesis cannot be used. In this
k
k
case, by fact 1, V (W ) = XW . But, XW ⊆ V (R), by definition. So, Tu,R
[W ∪R] = Tu,R
[R]. But R is equal
2 Vertex
3 Vertex

u in the proof corresponds to vertex x in the lemma, R to X, v to y, and Tv to Ty .
u in the proof corresponds to vertex x in the lemma and R to X.

9

1
to Tu,R
, because, for k = 1, algorithm Find Tree spanner on input (G, t) makes the call Find Subtree(G,
t, u, R, 1, ∅) and procedure Find Subtree returns R. Since partial solutions are never reduced during
k
k
k
k
the algorithm, R ⊆ Tu,R
. But Tu,R
is a tree, because of lemma 3. So, Tu,R
[W ∪ R] = Tu,R
[R] = R,
k+1
because the subgraph of a tree induced by the vertices of a subtree is the subtree. Therefore, Tv,S,u,R,W
is equal to (R ∪ S) \ ((R \ S) \ W ). By lemma 4, which “clears” the gray area in figure 1, it suffices to
prove that R ∪ S is a tree t-spanner of G[W ∪ S ∪ R]. Here, R ∪ S is a subtree of T , so it is a tree t-spanner
of G[S ∪ R]. But V (W ) ⊆ R in this case; so, G[S ∪ R] = G[W ∪ S ∪ R]. Therefore, the following holds.
k+1
Fact 3 Tv,S,u,R,W
is a tree t-spanner of G[W ∪ S], when H = ∅.

On the other hand, consider the case that H =
6 ∅. To prepare for formulations of induction
hypothesis, observe that R is closer than S to W . Formally, all the vertices in Tu are at T distance less
than or equal to k from v, because v is a k-center of Tu ∪ S. So, for each y ∈ YW , all vertices in Ty are
at T distance less than or equal to k − 1 from u. Also, all the vertices in R are at T distance less than
or equal to b 2t c from u. But in the induction step k ≥ b 2t c + 1; so, for each y ∈ YW , all the vertices in
Ty ∪ R are at T distance less than or equal to k − 1 from u (note that y ∈ R, so Ty ∪ R is connected).
Therefore4 ,
For each y ∈ YW , vertex u is a (k − 1)-center of Ty ∪ R
(7)

Vector (k − 1, u, R, Wy , y) satisfies the five conditions of the lemma for every y ∈ YW . To see this,
first, 1 ≤ b 2t c ≤ k − 1 ≤ |V (G)| − 2 and u ∈ G. Second, R has been defined appropriately. Third, y is
a T neighbor of u and Ty has been defined appropriately. Fourth, Wy has been defined appropriately.
Finally, fifth, u is a (k − 1)-center of Ty ∪ R (statement (7)). Therefore, since for every y ∈ YW the first
coordinate of vector (k − 1, u, R, Wy , y) is strictly less than k, theSinduction hypothesis states that the
conclusion of the lemma holds. Therefore,Sfor every component in y∈YW Wy the two statements in the
conclusion of the lemma hold. But H ⊆ y∈YW Wy . Let H be a component in H; then, H ∈ Wy0 H for
some yH ∈ YW . Therefore, by the induction hypothesis, for H, there is RH ⊆ G such that (see figure 4):
• Tyk−1
is contained in Ak−1
of algorithm Find Tree spanner(G, t) and
G
H ,RH

k
k
• Tu,R,y
is a tree t-spanner of G[H ∪ R], where Tu,R,y
is the graph (Tyk−1
[H ∪ RH ] ∪
H ,RH ,H
H ,RH ,H
H ,RH
R) \ ((RH \ R) \ H).

W

u
S
R

W

k
H1
Tu,R,y
H1 ,RH1 ,H1

k
H2
Tu,R,y
H2 ,RH2 ,H2

u
S

k
H3
Tu,R,y
H3 ,RH3 ,H3

R

TH1

H1

TH2

H2

TH3

H3

Figure 4: Part of the situation in the proof of lemma 5, as it is seen from two different angles. The shapes with
one circular end and one rectangular end correspond to auxiliary graphs. The small rectangle is S and the big
rectagle is component W of G \ S. The dashed circle is R; the dashed rectangles are components of G \ R, which
are the elements of H and are named as H1 , H2 , and H3 . Here, V (W ) = V ((W ∩ R) ∪ H1 ∪ H2 ∪ H3 ) (see fact 1).
The induction hypothesis dictates that there are three auxiliary graphs, which are shown on the left hand side,
k
that can help partial solution Tu,R
to cover H1 , H2 , and H3 . On the right hand side, three auxiliary graphs are
also shown but are these that procedure Find Subtree (see table 2) actually picked to increment partial solution
k
Tu,R
towards H1 , H2 , and H3 . Note that the pairwise intersection of the auxiliary graphs on each side is R; for
example, TH1 ∩ TH2 = R. As the proof continues, K = TH1 ∪ TH2 ∪ TH3 becomes the key element in proving the
lemma, when H 6= ∅.

Therefore, when procedure Find Subtree is called (line 7 of table 1) with input (G, t, u, R, k,
k−1
Ak−1
to satisfy the condition (line 20 of table 2) for incrementing
G ) there is at least one entry in AG
4 Note that if X is a connected subgraph of a tree T , then the X distance between a pair of vertices of X is equal to the
T distance between this pair of vertices.

10

lH
k
Tu,R
towards H; note that yH ∈ YW ⊆ NT (u) = NR (u). So (see figure 4), for some lH ≤ k, Tu,R
is
lH
incremented towards H and assume that the procedure picks TH = Tu,R,pH ,R(pH ,H),H to do so, where pH
−1
lH −1
is some R neighbor of u and TplH
belongs to AG
; i.e. TH is a tree t-spanner of G[H ∪R] and the
H ,R(pH ,H)

lH
lH
lH
lH
k
command Tu,R
= Tu,R
∪ TH is executed (lines 20 and 21 of table 2). Since TH ⊆ Tu,R
and Tu,R
⊆ Tu,R
,
k
auxiliary graph TH is a subgraph of Tu,R . All these auxiliary graphs that correspond to each H ∈ H
k
(which have been used by procedure Find Subtree to construct a part of Tu,R
) are put together in one
graph K. The following holds.
[
k
Let K =
TH . Then, K ⊆ Tu,R
(8)
H∈H

For each H ∈ H auxiliary graph TH is a connected graph, because it is a tree t-spanner of G[H ∪
k
R]. Also, all these auxiliary graphs share the vertices of R. So, K is a connected subgraph of Tu,R
k
k
(statement (8)). But Tu,R
is a tree t-spanner of G[Tu,R
], because of lemma 3. So, K is a tree t-spanner of
S
k
k
G[K]. Also, K coincides with Tu,R [K], because it is a subtree of tree Tu,R
. Here, V (K) = V (( H) ∪ R),
again because for each H ∈ H auxiliary graph TH is a tree t-spanner of G[H ∪ R]. Therefore, by fact 1,
V (K) = V (W ∪ R), because XW ⊆ V (R). So, K is a tree t-spanner of G[W ∪ R] and coincides with
k
Tu,R
[W ∪ R]. The following holds.
k
K = Tu,R
[W ∪ R] is a tree t-spanner of G[W ∪ R]

(9)

Set T2 = R ∪ S. Here, T2 is a connected subgraph of T ; so, T2 is a tree t-spanner of G[T2 ]. Lemma 2
will be used to prove that K ∪ T2 is a tree t-spanner of G[K ∪ T2 ], so the additional requirements for K
and T2 are shown5 . Assume, towards a contradiction, that there is an edge e0 of G between a vertex in
K \ T2 and a vertex in T2 \ K (a similar approach was taken in the proof of statement (4), where tree Tv
was defined to be the component of T \ {uv} that contains v). Here, V (K \ T2 ) is a subset of V (Tu \ R),
because V (W ) ⊆ V (Tu ) (here V (K) = V (W ∪ R) and R ⊆ T2 ). So, since Tv ∩ Tu = ∅, it holds that
V (K \ T2 ) ⊆ V ((G \ Tv ) \ R). Also, T2 \ K is equal to S \ R, because W being a component of G \ S avoids
S. Clearly, V (S \ R) is a subset of V (Tv \ R). Therefore, the existence of edge e0 is a contradiction to
lemma6 1. Here, K ∩ T2 is equal to R, which is a nonempty tree. Therefore, by lemma 2, K ∪ T2 is a tree
t-spanner of G[K ∪ T2 ]. But K ∪ T2 is equal to K ∪ S, because R ⊆ K. Therefore (see statement (9)),
the following holds.
k
K ∪ S = Tu,R
[W ∪ R] ∪ S is a tree t-spanner of G[W ∪ R ∪ S]

(10)

k+1
k
[W ∪ R] ∪ S) \ ((R \ S) \ W ); so, it remains to remove the gray area
Here, Tv,S,u,R,W
is equal to (Tu,R
in figure 1. Then, by statement (10) and lemma 4, the following holds.
k+1
Fact 4 Tv,S,u,R,W
is a tree t-spanner of G[W ∪ S], when H 6= ∅.

2

By facts 2, 3, and 4 the lemma holds.

To explain the time complexity of the algorithm, when graphs of bounded degree are inputs, the
following lemma binds the size of various sets used in For loops by functions of the maximum degree of
the input graph.
Lemma 6 Let G be a connected graph of maximum degree ∆ and t > 1 an integer. Then,
1. |Sv | ≤ 2∆

2+b t c
2

2. |Qv,S | ≤ ∆

, for every vertex v of G,

2+b 2t c

+ ∆, for every vertex v of G and for every S in Sv ,

3. |Ak−1
G | ≤ |V (G)| maxx∈V (G) |Sx |, for every k (2 ≤ k ≤ |V (G)|),
k−1
4. the number of Tu,R
∈ Ak−1
such that u ∈ NS (v) is at most ∆ maxx∈V (G) |Sx |, for every vertex v
G
of G, for every S in Sv , and for every k (2 ≤ k ≤ |V (G)|),
5 Here,

K corresponds to T1 of the lemma.
u in the proof corresponds to vertex x in the lemma, R to X, v to y, and Tv to Ty .

6 Vertex

11

k−1
where, Sv , Qv,S , Ak−1
G , and Tu,R are constructed in algorithm Find Tree spanner of tables 1 and 2 on
input (G, t).

Proof. First, let Gv be the sphere of G with center v and radius b 2t c. Let S be a member of Sv .
Since v is a b 2t c-center of S (line 5 of table 1), S must be a subgraph of Gv . Let Li denote the number
of vertices at G distance exactly i from v. Then L0 = 1. Also, Li ≤ ∆Li−1 , for i ≥ 1, because G has
maximum degree ∆ and each vertex at G distance i from v must be adjacent to a vertex at G distance
Pi=b t c
t
i − 1 from v. So, Gv has at most i=0 2 Li vertices. So, simply, Gv has at most ∆1+b 2 c + 1 vertices7 .
Therefore, since G has maximum degree ∆, Gv has at most ∆|V (Gv )|/2 edges. So, simply, Gv has at
t
most ∆2+b 2 c edges. At most |V (Gv )| − 1 edges can participate in S. So, roughly, considering the power
2+b t c

set of E(Gv ), the number of elements in Sv can be at most 2∆ 2 .
Second, any subtree S in Sv can have at most |V (Gv )| vertices. Then, as shown earlier, S can have
t
at most ∆1+b 2 c + 1 vertices. The number of edges of G with one endpoint in S and the other out of S
can be at most ∆|V (S)|, since G has maximum degree ∆. Then, since G is connected,8 the number of
t
components of G \ S is at most ∆2+b 2 c + ∆.
Third, for each vertex x of G, |Sx | partial solutions are in Ak−1
G , where 2 ≤ k ≤ |V (G)|. So,
k−1
|AG | ≤ |V (G)| maxx∈V (G) |Sx |.
Fourth, let v be a vertex of G and S a member of Sv . Then, since G has maximum degree ∆, v has
at most ∆ neighbors in S. But each vertex u of G is a central vertex of |Su | partial solutions. Therefore,
k−1
the number of Tu,R
∈ Ak−1
such that u ∈ NS (v) is at most ∆ maxx∈V (G) |Sx |, where 2 ≤ k ≤ |V (G)|. 2
G
Theorem 1 Let b, t be positive integers. There is an efficient algorithm to decide whether any graph G
with ∆(G) ≤ b admits a tree t-spanner.

Proof. If t = 1, then a graph admits a tree 1-spanner if and only if it is a tree. The empty graph
admits a tree t-spanner and a disconnected graph cannot admit a tree t-spanner. So, it remains to check
nonempty connected graphs for t > 1. For this, the algorithm described in this article is employed
and it is proved that a nonempty connected graph G admits a tree t-spanner if and only if algorithm
Find Tree spanner on input (G, t) returns a graph, where t > 1.
k
For the sufficiency proof, assume that algorithm Find Tree spanner on input (G, t) returns Tv,S
k
k
k
(line 9 of table 1). Then, V (G) = V (Tv,S ). But Tv,S is a tree t-spanner of G[Tv,S ], because of lemma 3.
Therefore, G admits a tree t-spanner.
For the necessity proof, assume that G admits a tree t-spanner T . Let v be a vertex of G and S be
the (v, b 2t c)T -sphere. Then, algorithm Find Tree spanner on input (G, t) calls procedure Find Subtree
with parameters (G, t, v, S, 1, A0G ) (line 7 of table 1); note that this happens even when G is the one
1
vertex graph. Then, procedure Find Subtree returns S (line 14 of table 2) which becomes Tv,S
.
On one hand, consider the case that Qv,S is empty (line 13 of table 2). Then, G contains no vertices
1
.
out of S; so, the algorithm returns Tv,S
On the other hand, consider the case that Qv,S is not empty. Assume, towards a contradiction,
that algorithm Find Tree spanner on input (G, t) does not return a graph. Then, for k = |V (G)| the
k
algorithm Find Tree spanner on input (G, t) does not return Tv,S
(line 9 of table 1). This means that
k
Tv,S does not contain the vertex set of some component W in Qv,S . This happens because (lines 17 to 21
k−1
of table 2) there is no vertex x ∈ NS (v) and RW ⊆ G, such that Tx,R
is contained in set Ak−1
and
G
W
k−1
k
k
Tv,S,x,RW ,W is a tree t-spanner of G[W ∪ S], where Tv,S,x,RW ,W = (Tx,RW [W ∪ RW ] ∪ S) \ ((RW \ S) \ W ).
But this is a contradiction to lemma 5; to see this, its five conditions are examined. First, 1 ≤ k − 1 ≤
|V (G)| − 1, because |V (G)| > 1 in this case; also, v ∈ V (G). Second, S is the (v, b 2t c)T -sphere. Third, let
u be a T neighbor of v that is in a T path from W to v; also, let Tu be the component of T \ {uv} that
contains u. Fourth, let W be the set {X ⊆ G : X is a component of G \ S and V (X) ⊆ V (Tu )}. Finally,
fifth, v is a (k − 1)-center of Tu ∪ S, even when G is a path and v an end vertex (k = |V (G)| and Tu ∪ S
is connected, because u ∈ S). Therefore, vector (k − 1, v, S, W, u) satisfies the conditions of lemma 5.
It suffices to prove that W ∈ W. By definition of vertex u, at least one vertex of W belongs to Tu .
Assume, towards a contradiction, that there is a vertex of W which is not in Tu . Then, since W is a
component of G \ S, there must be an edge of G from a vertex in Tu \ S to a vertex in (G \ Tu ) \ S. This
7 This

includes the ∆ ≤ 1 cases, because, then, Gv is the one vertex graph (∆ = 0) or has at most two vertices (∆ = 1).
algorithm works for disconnected graphs as well without increasing its time complexity. Here is the only place the
connectedness of the input graph is used. This facilitates the calculations for the running time of the algorithm.
8 The

12

is a contradiction to lemma9 1. Hence, W ∈ W. Therefore, by lemma 5 there is such a vertex x, namely
u, and such an RW ; a contradiction.
It remains to prove that the algorithm runs in polynomial time, when bounded degree graphs are
considered. Let n(G) be the number of vertices in G. Then, checking if the input to algorithm
Find Tree spanner is a connected nonempty graph G with ∆(G) ≤ b and t > 1 takes O(n) time.
For every vertex v ∈ G, |Sv | is O(1), because ∆(G) is bounded by constant b and t is a constant (see
lemma 6). So, procedure Find Subtree in table 2 is called O(n2 ) times.
Consider procedure Find Subtree on input (G, t, v, S, k, Ak−1
G ). The construction of Qv,S takes
O(n) time (G has a linear number of edges) and it is done only when k = 1. The commands in lines 16
to 22 of procedure Find Subtree in table 2 are executed when k > 1 and are examined one by one in
this paragraph. The number of partial solutions formed in the previous stage |Ak−1
G | is O(n) (lemma 6),
k−1
k−1
k−1
k
because |Sx | is O(1) for each vertex x ∈ G. Finding Tv,S in AG and doing the assignment Tv,S
= Tv,S
k−1
(line 16) takes O(n) time, because |AG | is O(n). Also, by lemma 6, |Qv,S | is O(1), because ∆(G) is
bounded by constant b and t is a constant (line 17). Next, it takes O(n) time to check sequentially all
k−1
k−1
k−1
elements of Ak−1
such that
G , because |AG | is O(n). Though, (line 18) the number of Tu,R ∈ AG
u ∈ NS (v) is O(1) (lemma 6), because ∆(G) is bounded by constant b and |Sx | is O(1) for each vertex
k−1
k
x ∈ G. Construction of Tu,R
[Q ∪ R] in line 19 takes O(n) time. To check whether Tv,S,u,R,Q
is a tree
t-spanner of G[Q ∪ S] in line 20 takes O(n) time, because ∆(G) is bounded by constant b and, therefore,
k
k
G[Q ∪ S] has a linear number of edges. Constructing the union of Tv,S
and Tv,S,u,R,Q
in line 21 takes
O(n) time. Finally, removing Q from Qv,S in line 22 can be done in linear time. Therefore, each call of
procedure Find Subtree takes O(n) time.
Returning back to algorithm Find Tree spanner (lines 7 to 9 of table 1), inserting the output of
k
procedure Find Subtree in AkG takes O(n) time. Next, checking whether V (G) = V (Tv,S
) and output
k
take O(n) time. All these three commands are executed O(n2 ) times, i.e. as many times as procedure
Tv,S
Find Subtree is called. Therefore, algorithm Find Tree spanner takes O(n3 ) time and it is efficient. 2

The t = 3 case

5

Let G be a graph. When t = 3, for every v in G, each S in Sv must have v as a 1-center, because
b 2t c = 1 (line 5 of table 1). This means that S is a tree with central vertex v and all its remaining
vertices are leaves. If the maximum degree of G is ∆, then S can have up to ∆ leaves. So, Sv can have
up to 2∆ members. So, if graphs with maximum degree at most b log n are considered as input to the
algorithm (where b is some constant), then, for each vertex v of the input graph, the size of Sv is at most
2b log n = nb . So, |Sv | is polynomially bounded by the number of vertices of the input graph n. Also, all
other sets considered in lemma 6 are polynomially bounded by n. So, for t = 3 and for every b > 0, the
algorithm runs in polynomial time and it is efficient, when graphs G with degrees less than b log |V (G)|
are examined.
As mentioned in the introduction, the problem had been solved for t = 2 on general graphs. Now, for
t > 3, a tree in Sv may contain vertices at distance 2 from v. This makes the size of Sv super-polynomial
in n in the worst case, when graphs with maximum degree at most b log n are considered. Therefore, the
algorithm is not efficient in this case.
There is some possibility, though, that the t = 4 case is similar to the t = 3 case. The diameter of
initial partial solutions (members of Sv , for each vertex v of the input graph G; line 5 of table 1) is at
most 2, when t = 3, while it is at most 4, when 4 ≤ t ≤ 5. One can well consider initial partial solutions
of diameter at most 3, when t = 4. Then10 , the tree 4-spanner admissibility of graphs with degrees less
than b log n (where b is a constant) may be decided efficiently too.
As mentioned in the proof of correctness (see figure 2), the t = 3 case exhibits some structural
differences as well, compared to the t > 3 cases. These differences may justify further investigation, in
an attempt to resolve the complexity status of the tree 3-spanner problem.
9 Vertex

v in the proof corresponds to vertex x in the lemma, S to X, u to y, and Tu to Ty .
diameter at most 3 subtree of a graph G consists of at most one central edge e and at most 2∆(G) edges sharing a
vertex with e. Therefore, the number of such subtrees with a given central edge is at most 22∆(G) .
10 A

13

6

Notes

Let us hint at the diversity of the tree spanners that the algorithm can produce, with a possible application. Assume that a tree t-spanner of a graph G is needed11 but it must contain certain edges of G.
Assume that these necessary edges form a tree A of diameter at most 2b 2t c. Hence, there is a vertex a
of G that is a b 2t c-center of A. Because of its small diameter, A is a tree t-spanner of G[A]. So, A will
be in Sa , when algorithm Find Tree spanner is run on input (G, t). To output only a suitable spanner,
line 9 of table 1 must be changed to
k
k
If (V (G) = V (Tv,S
) and S = A) Return(Tv,S
)}}

Then, the algorithm outputs a graph if and only if there is a tree t-spanner of G that contains A.
The only reason that the algorithm is not efficient for general graphs is the huge size of sets Sv even
for a few vertices v of the input graph G. A promising research direction is to consider a family of input
graphs for which one can prune these sets down to manageable sizes; i.e. when the algorithm constructs
set Sv for each vertex v of input graph G (line 5 of table 1), an efficient procedure may rule out many
subtrees of G that are not needed to build a final solution, because of some properties of G.

References
[1] Srinivasa Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel Smid, and Christos D.
Zaroliagis. Planar spanners and approximate shortest path queries among obstacles in the plane. In
Algorithms—ESA ’96 (Barcelona), pages 514–528. Springer, Berlin, 1996.
[2] Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804–823,
October 1985.
[3] Hans-Jürgen Bandelt and Andreas Dress. Reconstructing the shape of a tree from observed dissimilarity data. Adv. in Appl. Math., 7(3):309–343, 1986.
[4] J. A. Bondy. Trigraphs. Discrete Mathematics, 75:69–79, 1989.
[5] Andreas Brandstädt, Victor Chepoi, and Feodor Dragan. Distance approximating trees for chordal
and dually chordal graphs. J. Algorithms, 30(1):166–184, 1999.
[6] Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, and Van Bang Le. Tree spanners on chordal
graphs: complexity and algorithms. Theor. Comput. Sci., 310(1-3):329–354, 2004.
[7] Leizhen Cai. Tree Spanners: Spanning trees that approximate distances. PhD thesis, Department of
Computer Science, University of Toronto, 1992. (Available as Technical Report 260/92).
[8] Leizhen Cai and Derek G. Corneil. Tree spanners. SIAM J. of Discrete Mathematics, 8(3):359–378,
1995.
[9] L. Paul Chew. There are planar graphs almost as good as the complete graph. J. Comput. System
Sci., 39(2):205–219, 1989. Computational geometry.
[10] Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach. Automata, Languages and Programming:
35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part
I, chapter Spanners in Sparse Graphs, pages 597–608. Springer Berlin Heidelberg, Berlin, Heidelberg,
2008.
[11] Feodor F. Dragan and Ekkehard Köhler. An approximation algorithm for the tree t-spanner problem
on unweighted graphs via generalized chordal graphs. Algorithmica, 69(4):884–905, 2014.
[12] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary
metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485 – 497, 2004. Special
Issue on {STOC} 2003.
11 For example, a tree spanner of the underlying graph of a communication network is needed for broadcasting but some
connections (edges of the graph) are very reliable and they must be in the spanner.

14

[13] Sándor P. Fekete and Jana Kremer. Tree spanners in planar graphs. Discrete Appl. Math.,
108(1-2):85–103, 2001. International Workshop on Graph-Theoretic Concepts in Computer Science
(Smolenice Castle, 1998).
[14] Fedor V. Fomin, Petr A. Golovach, and Erik Jan van Leeuwen. Spanners of bounded degree graphs.
Inf. Process. Lett., 111(3):142–144, 2011.
[15] Dieter Kratsch, Hoang-Oanh Le, Haiko Mller, Erich Prisner, and Dorothea Wagner. Additive tree
spanners. SIAM JOURNAL ON DISCRETE MATHEMATICS, 17:2003, 1998.
[16] Hoàng-Oanh Le and Van Bang Le. Optimal tree 3-spanners in directed path graphs. Networks,
34(2):81–87, 1999.
[17] M. S. Mandanlal, G. Venkatesan, and C. Pandu Rangan. Tree 3-spanners on interval, permutation,
and regular bipartite graphs. Information Processing Letters, 59:97–102, 1996.
[18] Paul Manuel, Bharati Rajan, Indra Rajasingh, and Amutha Alaguvel. Tree spanners, cayley graphs,
and diametrically uniform graphs. In Graph-Theoretic Concepts in Computer Science, 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers, pages
334–345, 2003.
[19] Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, New
York, NY, USA, 2007.
[20] N.S. Narayanaswamy and G. Ramakrishna. Tree -spanners in outerplanar graphs via supply demand
partition. Discrete Applied Mathematics, 195:104 – 109, 2015. 12th Cologne-Twente Workshop on
Graphs and Combinatorial Optimization (CTW 2013).
[21] Ioannis Papoutsakis. Two structure theorems on tree spanners. Master’s thesis, Department of
Computer Science, University of Toronto, January 1999. (Available at TSpace of the University of
Toronto).
[22] Ioannis Papoutsakis. Tree Spanners of simple graphs. PhD thesis, Department of Computer Science,
University of Toronto, 2013. (Available at TSpace of the University of Toronto).
[23] Ioannis Papoutsakis. Tree 3-spanners of diameter at most 5. CoRR, abs/1402.3573:, 2014.
[24] Ioannis Papoutsakis. Tree spanners of small diameter. CoRR, abs/1503.06063:, 2014.
[25] Ioannis Papoutsakis. On approximating tree spanners that are breadth first search trees. Journal of
Computer and System Sciences, 82(5):817 – 825, 2016.
[26] D. Peleg and E. Upfal. A tradeoff between space and efficiency for routing tables. In STOC: ACM
Symposium on Theory of Computing (STOC), 1988.
[27] David Peleg and Eilon Reshef. Low complexity variants of the arrow distributed directory. Journal
of Computer and System Sciences, 63(3):474 – 485, 2001.
[28] David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput.,
18(4):740–747, 1989.
[29] S. Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1):7:1–7:22, 2009.
[30] Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in
graphs. Discrete Comput. Geom., 19(1):79–94, 1998.
[31] Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning,
graph sparsification, and solving linear systems. In Proceedings of the Thirty-sixth Annual ACM
Symposium on Theory of Computing, STOC ’04, pages 81–90, New York, NY, USA, 2004. ACM.
[32] G. Venkatesan, U. Rotics, M. S. Madanlal, J. A. Makowsky, and C. Pandu Rangan. Restrictions of
minimum spanner problems. Information and Computation, 136(2):143–164, 1997.
[33] D. B. West. Introduction to Graph Theory. Prentice Hall, Inc., 1996.

15

