Summary: For a pair of parameters \(\alpha,\beta \geq 1\), a spanning tree \(T\) of a weighted undirected \(n\)-vertex graph \(G = (V,E,w)\) is called an \((\alpha,\beta)\)-shallow-light tree (shortly, \((\alpha,\beta)\)-SLT) of \(G\) with respect to a designated vertex \(rt \in V\) if (1) it approximates all distances from \(rt\) to the other vertices up to a factor of \(\alpha\), and (2) its weight is at most \(\beta\) times the weight of the minimum spanning tree \(\mathrm{MST}(G)\) of \(G\). The parameter \(\alpha\) (resp., \(\beta\)) is called the root-distortion (resp., lightness) of the tree \(T\). Shallow-light trees (SLTs) constitute a fundamental graph structure, with numerous theoretical and practical applications. In particular, they were used for constructing spanners in network design, for VLSI-circuit design, for various data gathering and dissemination tasks in wireless and sensor networks, in overlay networks, and in the message-passing model of distributed computing.
Tight tradeoffs between the parameters of SLTs were established by B. Awerbuch et al. [“Cost-sensitive analysis of communication protocols”, in: PODC ’90 Proceedings of the ninth annual ACM symposium on Principles of distributed computing. New York: ACM, 177–187 [1990), “Efficient broadcast and light-weight spanners”, manuscript (1991)] and S. Khuller et al. [Algorithmica 14, No. 4, 305–321 (1995; Zbl 0833.68096)]. They showed that for any \(\epsilon > 0\) there always exist \((1+\epsilon,O(\frac{1}{\epsilon}))\)-SLTs and that the upper bound \(\beta = O(\frac{1}{\epsilon})\) on the lightness of SLTs cannot be improved. In this paper we show that using Steiner points one can build SLTs with logarithmic lightness, i.e., \(\beta = O(\log \frac{1}{\epsilon})\). This establishes an exponential separation between spanning SLTs and Steiner ones. In the regime \(\epsilon = 0\) our construction provides a shortest-path tree with weight at most \(O(\log n) \cdot w(\mathrm{MST}(G))\). Moreover, we prove matching lower bounds that show that all our results are tight up to constant factors.