Tree Spanners

A tree t-spanner T of a graph G is a spanning tree in which the distance between every pair of vertices is at most t times their distance in G. This notion is motivated by applications in communication networks, distributed systems, and network design. This paper studies graph-theoretic, algorithmic, and complexity issues about tree spanners. It is shown that a tree 1-spanner, if it exists, in a weighted graph with m edges and n vertices is a minimum spanning tree and can be found in O( mlog β ( m,n ) ) time, where β ( m,n ) = min \ i|log( i ) n ≤ m/n \. On the other hand, for any fixed $t > 1$, the problem of determining the existence of a tree t-spanner in a weighted graph is proven to be NP-complete. For unweighted graphs, it is shown that constructing a tree 2-spanner takes linear time, whereas determining the existence of a tree t-spanner is NP-complete for any fixed t ≥ 4. A theorem that captures the structure of tree 2-spanners is presented for unweighted graphs. For digraphs, an O( ( m + n )α ( m,n ) ) algorithm is provided for finding a tree t-spanner with t as small as possible, where α ( m,n ) is a functional inverse of Ackerman’s function. The results for tree spanners on undirected graphs are extended to “quasi-tree spanners” on digraphs. Furthermore, linear-time algorithms are derived for verifying tree spanners and quasi-tree spanners.