Corelab Seminar

Ioannis Papoutsakis (University of Toronto)
Tree Spanners of small diameter

A tree t-spanner of a graph is a subtree of the graph such that for each pair of vertices their distance in the tree is at most t times their distance in the graph. Such a problem is NP complete for t>3 and tractable for t<3; while the situation for t=3 is unresolved.

If a graph admits a spanning tree of diameter at most t, then it trivially admits a tree t-spanner as well. In this talk we move one step away form the trivial case and for each t we examine the problem of whether a graph admits a tree t-spanner of diameter at most t+1. It is shown that such a problem is NP complete for t>3 and its efficiently solvable for t<4.