Spanning and Metric Tree Covers Parameterized by Treewidth
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917069671366656 |
|---|---|
| author | Elkin, Michael Shabat, Idan |
| author_facet | Elkin, Michael Shabat, Idan |
| contents | Given a graph $G=(V,E)$, a tree cover is a collection of trees $\mathcal{T}=\{T_1,T_2,...,T_q\}$, such that for every pair of vertices $u,v\in V$ there is a tree $T\in\mathcal{T}$ that contains a $u-v$ path with a small stretch. If the trees $T_i$ are sub-graphs of $G$, the tree cover is called a spanning tree cover. If these trees are HSTs, it is called an HST cover.
In a seminal work, Mendel and Naor [2006] showed that for any parameter $k=1,2,...$, there exists an HST cover, and a non-spanning tree cover, with stretch $O(k)$ and with $O(kn^{\frac{1}{k}})$ trees. Abraham et al. [2020] devised a spanning version of this result, albeit with stretch $O(k\log\log n)$. For graphs of small treewidth $t$, Gupta et al. [2004] devised an exact spanning tree cover with $O(t\log n)$ trees, and Chang et al. [2-23] devised a $(1+ε)$-approximate non-spanning tree cover with $2^{(t/ε)^{O(t)}}$ trees.
We prove a smooth tradeoff between the stretch and the number of trees for graphs with balanced recursive separators of size at most $s(n)$ or treewidth at most $t(n)$. Specifically, for any $k=1,2,...$, we provide tree covers and HST covers with stretch $O(k)$ and $O\left(\frac{k^2\log n}{\log s(n)}\cdot s(n)^{\frac{1}{k}}\right)$ trees or $O(k\log n\cdot t(n)^{\frac{1}{k}})$ trees, respectively. We also devise spanning tree covers with these parameters and stretch $O(k\log\log n)$. In addition devise a spanning tree cover for general graphs with stretch $O(k\log\log n)$ and average overlap $O(n^{\frac{1}{k}})$.
We use our tree covers to provide improved path-reporting spanners, emulators (including low-hop emulators, known also as low-hop metric spanners), distance labeling schemes and routing schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06263 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spanning and Metric Tree Covers Parameterized by Treewidth Elkin, Michael Shabat, Idan Data Structures and Algorithms Given a graph $G=(V,E)$, a tree cover is a collection of trees $\mathcal{T}=\{T_1,T_2,...,T_q\}$, such that for every pair of vertices $u,v\in V$ there is a tree $T\in\mathcal{T}$ that contains a $u-v$ path with a small stretch. If the trees $T_i$ are sub-graphs of $G$, the tree cover is called a spanning tree cover. If these trees are HSTs, it is called an HST cover. In a seminal work, Mendel and Naor [2006] showed that for any parameter $k=1,2,...$, there exists an HST cover, and a non-spanning tree cover, with stretch $O(k)$ and with $O(kn^{\frac{1}{k}})$ trees. Abraham et al. [2020] devised a spanning version of this result, albeit with stretch $O(k\log\log n)$. For graphs of small treewidth $t$, Gupta et al. [2004] devised an exact spanning tree cover with $O(t\log n)$ trees, and Chang et al. [2-23] devised a $(1+ε)$-approximate non-spanning tree cover with $2^{(t/ε)^{O(t)}}$ trees. We prove a smooth tradeoff between the stretch and the number of trees for graphs with balanced recursive separators of size at most $s(n)$ or treewidth at most $t(n)$. Specifically, for any $k=1,2,...$, we provide tree covers and HST covers with stretch $O(k)$ and $O\left(\frac{k^2\log n}{\log s(n)}\cdot s(n)^{\frac{1}{k}}\right)$ trees or $O(k\log n\cdot t(n)^{\frac{1}{k}})$ trees, respectively. We also devise spanning tree covers with these parameters and stretch $O(k\log\log n)$. In addition devise a spanning tree cover for general graphs with stretch $O(k\log\log n)$ and average overlap $O(n^{\frac{1}{k}})$. We use our tree covers to provide improved path-reporting spanners, emulators (including low-hop emulators, known also as low-hop metric spanners), distance labeling schemes and routing schemes. |
| title | Spanning and Metric Tree Covers Parameterized by Treewidth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.06263 |