Lower Bounds on Tree Covers

Abstract. Given an [Formula: see text]-point metric space [Formula: see text], a tree cover [Formula: see text] is a set of [Formula: see text] trees on [Formula: see text] such that every pair of vertices in [Formula: see text] has a low-distortion path in one of the trees in [Formula: see text]. 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 [Formula: see text] and distortion. When [Formula: see text], the best distortion is known to be [Formula: see text]. For a constant [Formula: see text], the best distortion upper bound is [Formula: see text] and the strongest lower bound is [Formula: see text], leaving a gap to be closed. In this paper, we improve the lower bound to [Formula: see text]. 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.