Given an n-point metric space (X, dX), a tree cover 𝒯 is a set of |𝒯| = k trees on X such that every pair of vertices in X has a low-distortion path in one of the trees in 𝒯. 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 ≥ 2, the best distortion upper bound is Õ (n^1/k) and the strongest lower bound is Ω (logₖ n), leaving a gap to be closed. In this paper, we improve the lower bound to Ω (n^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.
Chen et al. (Thu,) studied this question.