Euclidean Steiner shallow-light trees

Shay Solomon



$\newcommand{\eps}{\epsilon}$A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an $(\alpha,\beta)$-SLT of a weighted undirected graph $G = (V,E,w)$ with respect to a designated vertex $rt\in V$ is a spanning tree of $G$ with: (1) root-stretch $\alpha$ – it preserves all distances between $rt$ and the other vertices up to a factor of $\alpha$, and (2) lightness $\beta$ – it has weight at most $\beta$ times the weight of a minimum spanning tree $MST(G)$ of $G$.

Tight tradeoffs between the parameters of SLTs were established by Awerbuch et al. in PODC'90 and by Khuller et al. in SODA'93. They showed that for any $\eps > 0$, any graph admits a $(1+\eps,O(\frac{1}{\eps}))$-SLT with respect to any root vertex, and complemented this result with a matching lower bound.

Khuller et al. asked if the upper bound $\beta = O(\frac{1}{\eps})$ on the lightness of SLTs can be improved in Euclidean spaces. In FOCS'11 Elkin and this author gave a negative answer to this question, showing a lower bound of $\beta = \Omega(\frac{1}{\eps})$ that applies to 2-dimensional Euclidean spaces.

In this paper we show that Steiner points lead to a quadratic improvement in Euclidean SLTs, by presenting a construction of Euclidean Steiner $(1+\eps,O(\sqrt{\frac{1}{\eps})})$-SLTs in arbitrary 2-dimensional Euclidean spaces. The lightness bound $\beta = O(\sqrt{\frac{1}{\eps}})$ of our construction is optimal up to a constant. The runtime of our construction, and thus the number of Steiner points used, are bounded by $O(n)$.

Full Text:



ISSN: 1920-180X