Improved Euclidean Shallow Light Trees

Abstract

For parameters $\alpha ,\beta \ge 1$, a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(\alpha ,\beta )$-shallow-light tree (SLT) if (i) for every vertex $v$, $d_T(r,v)\le \alpha \cdot d_G(r,v)$ (root-stretch $\alpha$), and (ii) $w(T)\le \beta \cdot w(\mathsf{MST})$ (lightness $\beta$). The pioneering work of Khuller, Raghavachari, and Young (SODA 1993) constructed $\left(1+\epsilon ,\frac{2}{\epsilon }+1\right)$-SLTs for general weighted graphs, and proved that this tradeoff between root-stretch and lightness is tight even for series-parallel graphs. They further asked whether even a slight improvement, namely reducing the lightness to $\frac{2-c}{\epsilon }$ for any constant $c>0$, is possible in the Euclidean plane. We resolve this longstanding question in the affirmative. Specifically, we show that every Euclidean instance admits an SLT with root-stretch $1+\epsilon$ and lightness at most $\left(\frac{5}{3}+o_{\epsilon }(1)\right)\cdot \frac{1}{\epsilon }$, thereby significantly improving upon the longstanding $2/\epsilon$ barrier. As our second main result, we provide a construction of SLTs in the Euclidean plane, with root stretch $1+\epsilon$ and lightness at most $\left(\frac{2\pi }{\sqrt{4{\pi }^2+1}}+o_{\epsilon }(1)\right)\frac{1}{\epsilon }\approx (0.987+o_{\epsilon }(1))\frac{1}{\epsilon }$. Notably, this reduces the leading $2/\epsilon$ term in the lightness bound by more than a factor of two, and comes quite close to the lower bound of $\left(\frac{2\pi }{2\pi +1}+o_{\epsilon }(1))\right)\cdot \frac{1}{\epsilon }\approx (0.862+o_{\epsilon }(1))\frac{1}{\epsilon }$ by Elkin and Solomon (FOCS 2011).

Abstract truncated to meet arxiv characters limit