Tree spanner

A tree k-spanner (or simply k-spanner) of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most k times their distance in G.

Known Results

There are several papers written on the subject of tree spanners. One of these was entitled Tree Spanners written by mathematicians Leizhen Cai and Derek Corneil, which explored theoretical and algorithmic problems associated with tree spanners. Some of the conclusions from that paper are listed below:

Theorem 1

If H is the spanning subgraph of a weighted graph G=(V,E;w), then these statements are equivalent:

(a) H is a t-spanner of G for every pair of vertices x and y of G.

(b) For every edge xy in V, d_H(x;y) ≤ t × d_G(x;y).

(c) For every edge xy in E\E(H), d_H(x;y) ≤ t × d_G(x; y).

(d) For every edge xy in E, d_H(x;y) ≤ t × w(xy).

(e) For every edge xy in E\E(H), d_H(x;y) ≤ t × w(xy).

Observation: Let F be a t-spanner of G and H be a k-spanner of F. Then H is a kt-spanner of G.

Observation: For any k > 1, H = (V;E';w) is a t-spanner of G = (V;E;w) iff H' = (V;E';w') is a t-spanner of G' = (V;E;w'), where w'(e) = k × w(e) for every e ∈ E.

Observation: Let T be a spanning tree of a graph G. Then T is a tree t-spanner of G iff for every block H of G, T ∩ H is a tree t-spanner of H.

Observation 1.5 Let H be a spanning subgraph of an unweighted graph G. Then H is a t-spanner iff H is a ⌊t⌋-spanner.

Theorem 2

Let D and G be directed and undirected weighted graphs respectively, S and T be spanning trees of D and G,and Q be a quasitree of D. The following problems can be solved in O(m) time.

(a) Determine the stretch index of T.

(b) Is S a tree spanner?

(c) Is Q a quasitree spanner?

Lemma: Let H be a 1-spanner of a weighted graph G. Then H is minimal iff d_H-xy(x;y) > w(xy) for every edge xy of H.

Theorem 3

Let H be a minimal 1-spanner of a weighted graph G, and let xy be an edge of G. The following statements are equivalent:

(a) The edge xy belongs to H.

(b) For every vertex z in V\{x,y}, d_G(x;z) + d_G(z;y) > w(xy)

(c) The distance d_G-xy(x;y) > w(xy)

Theorem 4

The minimum (or optimal) 1-spanner of a weighted graph can be found in O(mn + n2log n) time.

Theorem 5

The tree 1-spanner of a weighted graph G is a minimum spanning tree. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree.

Theorem 6

The tree 1-spanner of a weighted graph can be found in O(mlog,(m;n)) time.

Theorem 7

For any fixed rational number t > 1, it is NP-complete to determine whether a weighted graph contains a tree t-spanner, even if all edge weights are positive integers.

Corollary: For any fixed rational number t > 1, it is NP-complete to determine,given a weighted graph G and a positive integer K, whether G contains a t-spanner with at most K edges, even if all edge weights are positive integers.

Corollary: For any fixed rational number t > 1, it is NP-complete to determine,given a weighted graph G and a positive rational number W, whether G contains a t-spanner of total weight at most W, even if all edge weights are positive integers.

Theorem 8

For any fixed t > 4, the tree t-spanner problem is NP-complete.

Theorem 9

Let G be a nonseparable graph. Then a spanning tree T of G is a tree 2-spanner i for each triconnected component H of G, T \H is a spanning star of H.

Corollary: A triconnected graph G admits a tree 2-spanner i it contains a universal vertex.

Theorem 10

A tree 2-spanner (if it exists) of a graph can be found in O(m + n) time.

References

• Handke, Dagmar; Kortsarz, Guy (2000), "Tree spanners for subgraphs and related tree covering problems", Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1928, pp. 206–217, doi:10.1007/3-540-40064-8_20.