Tree spanners on chordal graphs: complexity and algorithms (Q1884978)

A spanning tree \(T\) of a graph \(G\) is called \(t\)-multiplicative tree spanner (tree \(t\)-spanner for short) if \(d_T(u,v) \leq t \cdot d_G(u,v)\) holds for all vertices \(u\) and \(v\). The tree \(t\)-spanner problem asks whether a graph admits a tree \(t\)-spanner. Strengthening a result by \textit{L. Cai} and \textit{D. G. Corneil} [SIAM J. Discrete Math. 8, No. 3, 359--387 (1995; Zbl 0832.05037)] it is shown that, for any \(t \geq 4\), the tree \(t\)-spanner problem is NP-complete when restricted to chordal graphs of diameter at most \(2\lceil t/2\rceil+1\). For \(t \geq 2\), if every chordal graph of diameter at most \(2\lfloor t/2\rfloor-1\) has a tree \(t\)-spanner then it can be constructed in linear time. Restrictions to subclasses of chordal graphs are considered as well.