Improved Euclidean Shallow Light Trees
2026-08-04 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors study special spanning trees called shallow-light trees (SLTs) in weighted graphs, focusing on the Euclidean plane. These trees balance how short paths from a root to other vertices are (root-stretch) and the total tree weight compared to a minimum spanning tree (lightness). Previous work established a tight tradeoff between these two goals, but the authors improve this by showing better constructions with lower lightness for small stretch in Euclidean spaces. Their new trees reduce the lightness factor significantly below the known barrier of 2/ε and approach known lower bounds. This answers an open question about whether Euclidean graphs allow better SLT tradeoffs than general graphs.
shallow-light treespanning treeroot-stretchlightnessminimum spanning treeEuclidean graphapproximation tradeoffweighted graphgraph algorithmsgeometry in graphs
Authors
Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang
Abstract
For parameters $α,β\geq 1$, a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(α,β)$-shallow-light tree (SLT) if (i) for every vertex $v$, $d_T(r,v) \leq α\cdot d_G(r,v)$ (root-stretch $α$), and (ii) $w(T) \leq β\cdot w(\mathsf{MST})$ (lightness $β$). The pioneering work of Khuller, Raghavachari, and Young (SODA 1993) constructed $\left(1+ε, \tfrac{2}ε+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 $\tfrac{2-c}ε$ 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+ε$ and lightness at most $\left(\frac{5}{3} + o_ε(1)\right) \cdot \frac{1}ε$, thereby significantly improving upon the longstanding $2/ε$ barrier. As our second main result, we provide a construction of SLTs in the Euclidean plane, with root stretch $1+ε$ and lightness at most $\left(\frac{2π}{\sqrt{4π^2+1}}+o_ε(1)\right)\frac{1}ε \approx (0.987+o_ε(1))\frac{1}ε$. Notably, this reduces the leading $2/ε$ term in the lightness bound by more than a factor of two, and comes quite close to the lower bound of $\left(\frac{2π}{2π+1} +o_ε(1))\right) \cdot \frac{1}ε \approx (0.862 +o_ε(1))\frac{1}ε$ by Elkin and Solomon (FOCS 2011).