树覆盖的下界 (Lower Bounds on Tree Covers)

Given an $n$-point metric space $(X,d_X)$, a tree cover $\mathcal{T}$ is a set of $|\mathcal{T}|=k$ trees on $X$ such that every pair of vertices in $X$ has a low-distortion path in one of the trees in $\mathcal{T}$. Tree covers have been playing a crucial role in graph algorithms for decades, and the research focus is the construction of tree covers with small size $k$ and distortion. When $k=1$, the best distortion is known to be $Θ(n)$. For a constant $k\ge 2$, the best distortion upper bound is $\tilde O(n^{\frac 1 k})$ and the strongest lower bound is $Ω(\log_k n)$, leaving a gap to be closed. In this paper, we improve the lower bound to $Ω(n^{\frac{1}{2^{k-1}}})$. Our proof is a novel analysis on a structurally simple grid-like graph, which utilizes some combinatorial fixed-point theorems. We believe that they will prove useful for analyzing other tree-like data structures as well.

翻译：给定一个 $n$ 点度量空间 $(X,d_X)$，树覆盖 $\mathcal{T}$ 是 $X$ 上 $|\mathcal{T}|=k$ 棵树的集合，使得 $X$ 中任意一对顶点在 $\mathcal{T}$ 的某棵树中存在一条低失真路径。数十年来，树覆盖在图算法中一直扮演着关键角色，研究重点在于构造具有较小规模 $k$ 和失真的树覆盖。当 $k=1$ 时，已知最佳失真为 $Θ(n)$。对于常数 $k\ge 2$，最佳失真上界为 $\tilde O(n^{\frac 1 k})$，而最强下界为 $Ω(\log_k n)$，两者之间存在待填补的间隙。本文中，我们将下界改进至 $Ω(n^{\frac{1}{2^{k-1}}})$。我们的证明基于对结构简单的网格状图进行新颖分析，并运用了一些组合不动点定理。我们相信这些方法对于分析其他树状数据结构也将具有实用价值。