{"ID":2844296,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06263","arxiv_id":"2511.06263","title":"Spanning and Metric Tree Covers Parameterized by Treewidth","abstract":"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.","short_abstract":"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. I...","url_abs":"https://arxiv.org/abs/2511.06263","url_pdf":"https://arxiv.org/pdf/2511.06263v1","authors":"[\"Michael Elkin\",\"Idan Shabat\"]","published":"2025-11-09T07:55:58Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}