Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.14918 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914210902966272 |
|---|---|
| author | Le, Hung Milenković, Lazar Solomon, Shay Than, Cuong |
| author_facet | Le, Hung Milenković, Lazar Solomon, Shay Than, Cuong |
| contents | Sparse shortcuttings of trees -- equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter -- have been studied extensively (under different names and settings), since the pioneering works of [Yao82, Cha87, AS87, BTS94], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Yao82, Cha87, AS87, BTS94] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for $n$-node trees with sparsity $O(\log^* n)$. Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity $Ω(\log n)$), which is a significant drawback for many applications.
We initiate a systematic study of constant-hop tree shortcuttings that are ``tree-like''. We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold.
* New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to $O(\log\log n)$. We also provide a lower bound for larger values of $k$, which together yield $\text{hop-diameter}\times \text{treewidth} = Ω((\log\log n)^2)$ for all values of hop-diameter, resolving an open question of [FL22, Le23]. [...] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_14918 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tree-Like Shortcuttings of Trees Le, Hung Milenković, Lazar Solomon, Shay Than, Cuong Data Structures and Algorithms Sparse shortcuttings of trees -- equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter -- have been studied extensively (under different names and settings), since the pioneering works of [Yao82, Cha87, AS87, BTS94], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Yao82, Cha87, AS87, BTS94] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for $n$-node trees with sparsity $O(\log^* n)$. Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity $Ω(\log n)$), which is a significant drawback for many applications. We initiate a systematic study of constant-hop tree shortcuttings that are ``tree-like''. We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold. * New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to $O(\log\log n)$. We also provide a lower bound for larger values of $k$, which together yield $\text{hop-diameter}\times \text{treewidth} = Ω((\log\log n)^2)$ for all values of hop-diameter, resolving an open question of [FL22, Le23]. [...] |
| title | Tree-Like Shortcuttings of Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.14918 |