2026-07-23T14:40:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23407 2025-10-02T12:54:18Z ddc:004 open_access

Light Spanners with Small Hop-Diameter Bhore, Sujoy Milenković, Lazar Geometric Spanners Lightness Hop-Diameter Recurrences Lower Bounds Lightness, sparsity, and hop-diameter are the fundamental parameters of geometric spanners. Arya et al. [STOC'95] showed in their seminal work that there exists a construction of Euclidean (1+ε)-spanners with hop-diameter O(log n) and lightness O(log n). They also gave a general tradeoff of hop-diameter k and sparsity O(α_k(n)), where α_k is a very slowly growing inverse of an Ackermann-style function. The former combination of logarithmic hop-diameter and lightness is optimal due to the lower bound by Dinitz et al. [FOCS'08]. Later, Elkin and Solomon [STOC'13] generalized the light spanner construction to doubling metrics and extended the tradeoff for more values of hop-diameter k. In a recent line of work [SoCG'22, SoCG'23], Le et al. proved that the aforementioned tradeoff between the hop-diameter and sparsity is tight for every choice of hop-diameter k. A fundamental question remains: What is the optimal tradeoff between the hop-diameter and lightness for every value of k? In this paper, we present a general framework for constructing light spanners with small hop-diameter. Our framework is based on tree covers. In particular, we show that if a metric admits a tree cover with γ trees, stretch t, and lightness L, then it also admits a t-spanner with hop-diameter k and lightness O(kn^{2/k}⋅ γ L). Further, we note that the tradeoff for trees is tight due to a construction in uniform line metric, which is perhaps the simplest tree metric. As a direct consequence of this framework, we obtain new tradeoffs between lightness and hop-diameter for doubling metrics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Lazar Milenković 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.30 urn:nbn:de:0030-drops-234075 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode