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.

翻译：给定图$G=(V,E)$，树覆盖是指树的集合$\mathcal{T}=\{T_1,T_2,...,T_q\}$，使得对于任意顶点对$u,v\in V$，存在树$T\in\mathcal{T}$包含一条具有较小拉伸的$u-v$路径。若树$T_i$是$G$的子图，则称为生成树覆盖；若这些树是层次生成树（HST），则称为HST覆盖。在开创性工作中，Mendel与Naor[2006]证明对于任意参数$k=1,2,...$，存在具有$O(k)$拉伸和$O(kn^{\frac{1}{k}})$棵树的HST覆盖及非生成树覆盖。Abraham等人[2020]提出了该结果的生成版本，但其拉伸为$O(k\log\log n)$。对于树宽$t$较小的图，Gupta等人[2004]设计了具有$O(t\log n)$棵树的精确生成树覆盖，Chang等人[2-23]设计了具有$2^{(t/ε)^{O(t)}}$棵树的$(1+ε)$近似非生成树覆盖。本文证明了具有最大平衡递归分隔器规模$s(n)$或最大树宽$t(n)$的图在拉伸与树数量之间的平滑权衡。具体而言，对于任意$k=1,2,...$，我们分别构造了具有$O(k)$拉伸和$O\left(\frac{k^2\log n}{\log s(n)}\cdot s(n)^{\frac{1}{k}}\right)$棵树或$O(k\log n\cdot t(n)^{\frac{1}{k}})$棵树的树覆盖与HST覆盖，同时设计了具有相同参数和$O(k\log\log n)$拉伸的生成树覆盖。此外，我们为一般图构造了具有$O(k\log\log n)$拉伸和$O(n^{\frac{1}{k}})$平均重叠度的生成树覆盖。利用这些树覆盖，我们进一步改进了路径报告型稀疏器、仿真器（包括低跳仿真器，亦称低跳度量稀疏器）、距离标记方案与路由方案。