Tree spanner

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

There are several papers written on the subject of tree spanners. One of these was entitled Tree Spanners^[1] 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. ${\displaystyle n}${\displaystyle n} is always the number of vertices of the graph, and ${\displaystyle m}${\displaystyle m} is its number of edges.

1. A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}${\displaystyle {\mathcal {O}}(m\log \beta (m,n))} time (in terms of complexity) for a weighted graph, where ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\right\}}${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\right\}}. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree.
2. A tree 2-spanner can be constructed in ${\displaystyle {\mathcal {O}}(m+n)}${\displaystyle {\mathcal {O}}(m+n)} time, and the tree ${\displaystyle t}${\displaystyle t}-spanner problem is NP-complete for any fixed integer ${\displaystyle t>3}${\displaystyle t>3}.
3. The complexity for finding a minimum tree spanner in a digraph is ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}, where ${\displaystyle \alpha (m+n,n)}${\displaystyle \alpha (m+n,n)} is a functional inverse of the Ackermann function
4. The minimum 1-spanner of a weighted graph can be found in ${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))} time.
5. For any fixed rational number ${\displaystyle t>1}${\displaystyle 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.
6. A tree spanner (or a minimum tree spanner) of a digraph can be found in linear time.
7. A digraph contains at most one tree spanner.
8. The quasi-tree spanner of a weighted digraph can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}${\displaystyle {\mathcal {O}}(m\log \beta (m,n))} time.

• Graph spanner
• Geometric spanner

• 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, ISBN 978-3-540-41183-3 .

• Spanning tree
• NP-complete problems