LOWER BOUNDS ON TREE COVERS

Given an n-point metric space (X,d_x), 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 Ω(n1/k), leaving a gap to be closed. In this paper, we improve the lower bound to Ω(Formula Presented). 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.