Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.22669 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910898204966912 |
|---|---|
| author | Chang, Hsien-Chih Conroy, Jonathan Le, Hung Solomon, Shay Than, Cuong |
| author_facet | Chang, Hsien-Chih Conroy, Jonathan Le, Hung Solomon, Shay Than, Cuong |
| contents | A $(1+\varepsilon)$-stretch tree cover of an edge-weighted $n$-vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with a constant number of trees, where the constant depends on $\varepsilon$ and the dimension $d$. This result was generalized for arbitrary doubling metrics by Bartal et. al. [ICALP'19]. While the total number of edges in the tree covers of Arya et. al. and Bartal et. al. is $O(n)$, all known tree cover constructions incur a total lightness of $Ω(\log n)$; whether one can get a tree cover of constant lightness has remained a longstanding open question, even for 2-dimensional point sets.
In this work we resolve this fundamental question in the affirmative, as a direct corollary of a new construction of $(1+\varepsilon)$-stretch spanning tree cover for doubling graphs; in a spanning tree cover, every tree may only use edges of the input graph rather than the corresponding metric. To the best of our knowledge, this is the first constant-stretch spanning tree cover construction (let alone for $(1+\varepsilon)$-stretch) with a constant number of trees, for any nontrivial family of graphs.
Concrete applications of our spanning tree cover include a $(1+\varepsilon)$-stretch light tree cover, a compact $(1+\varepsilon)$-stretch routing scheme in the labeled model, and a $(1+\varepsilon)$-stretch path-reporting distance oracle, for doubling graphs. [...] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22669 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs Chang, Hsien-Chih Conroy, Jonathan Le, Hung Solomon, Shay Than, Cuong Data Structures and Algorithms A $(1+\varepsilon)$-stretch tree cover of an edge-weighted $n$-vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with a constant number of trees, where the constant depends on $\varepsilon$ and the dimension $d$. This result was generalized for arbitrary doubling metrics by Bartal et. al. [ICALP'19]. While the total number of edges in the tree covers of Arya et. al. and Bartal et. al. is $O(n)$, all known tree cover constructions incur a total lightness of $Ω(\log n)$; whether one can get a tree cover of constant lightness has remained a longstanding open question, even for 2-dimensional point sets. In this work we resolve this fundamental question in the affirmative, as a direct corollary of a new construction of $(1+\varepsilon)$-stretch spanning tree cover for doubling graphs; in a spanning tree cover, every tree may only use edges of the input graph rather than the corresponding metric. To the best of our knowledge, this is the first constant-stretch spanning tree cover construction (let alone for $(1+\varepsilon)$-stretch) with a constant number of trees, for any nontrivial family of graphs. Concrete applications of our spanning tree cover include a $(1+\varepsilon)$-stretch light tree cover, a compact $(1+\varepsilon)$-stretch routing scheme in the labeled model, and a $(1+\varepsilon)$-stretch path-reporting distance oracle, for doubling graphs. [...] |
| title | Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.22669 |