Light Spanners with Small Hop-Diameter
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908353103396864 |
|---|---|
| author | Bhore, Sujoy Milenkovic, Lazar |
| author_facet | Bhore, Sujoy Milenkovic, Lazar |
| contents | 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+\varepsilon)$-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}\cdot γ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 a tight tradeoff between lightness and hop-diameter for doubling metrics in the entire regime of $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04536 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Light Spanners with Small Hop-Diameter Bhore, Sujoy Milenkovic, Lazar Data Structures and Algorithms Computational Geometry 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+\varepsilon)$-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}\cdot γ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 a tight tradeoff between lightness and hop-diameter for doubling metrics in the entire regime of $k$. |
| title | Light Spanners with Small Hop-Diameter |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2505.04536 |