Lower Bounds on Tree Covers
Yu Chen, Zihan Tan, Hangyu Xu · 2025
Read Lower Bounds on Tree Covers by Yu Chen, Zihan Tan, Hangyu Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10376.txt.
Introduction
Yu Chen, Zihan Tan, and Hangyu Xu tackle an open problem in computer science in this 2025 paper. A tree cover is a small set of trees drawn over a set of points, so that some tree always gives a short route between any two points. Such covers have served graph algorithms for decades, and builders want few trees with little stretch.
For two or more trees, the best stretch anyone could build and the lowest stretch anyone could prove sat far apart. The authors narrow that gap with a stronger lower bound, proved on a simple grid-like graph. Their proof leans on fixed-point theorems from combinatorics, tools they expect will help study other tree-like structures too.
Catalog record
| CREATOR | Yu Chen, Zihan Tan, Hangyu Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-10376
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower Bounds on Tree Covers Yu Chen, Zihan Tan, Hangyu Xu Abstract Given an n n -point metric space ( X , d X ) (X,d_{X}) , a tree cover 𝒯 {\mathcal{T}} is a set of | 𝒯 | = k |{\mathcal{T}}|=k trees on X X such that every pair of vertices in X 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 k and distortion. When k = 1 k=1 , the best distortion is known to be Θ ( n ) \Theta(n) . For a constant k ≥ 2 k\geq 2 , the best distortion upper bound is O ~ ( n 1 k ) \tilde{O}(n^{\frac{1}{k}}) and the strongest lower bound is Ω ( log k n ) \Omega(\log_{k}n) , leaving a gap to be closed. In this paper, we improve the lower bound to Ω ( n 1 2 k − 1 ) \Omega(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. 1 Introduction Given a metric space (X,d_{X}) on |X|=n points, an (\alpha,k) -tree cover is a collection {\mathcal{T}}=\left\{T_{1},\ldots,T_{k}\right\} of k (edge-weighted trees) on X , such that every pair x,y of vertices in X , • for each 1\leq i\leq k , \mathrm{dist}_{T_{i}}(x,y)\geq d_{X}(x,y) (that is, each T_{i} is a dominating tree ); and • there exists an 1\leq i\leq k , such that \mathrm{dist}_{T_{i}}(x,y)\leq\alpha\cdot d_{X}(x,y) . The integer k=|{\mathcal{T}}| is called the size of {\mathcal{T}} and the real number \alpha\geq 1 is called the distortion or stretch of {\mathcal{T}} . The goal is to construct tree covers with small size and distortion. As a natural and instrumental approach to approximating metrics by trees, tree cover has been studied extensively and has found numerous algorithmic applications, for example, approximating low-dimensional Euclidean spaces [ ADM+95 , CCL+24a ] , routing [ AP92 , GKR01 , AKP02 , CGMZ16 ] , network design [ GHR06 ] , distance oracles [ MN07 ] , Ramsey tree covers [ BLMN03 , BFN22 ] , Steiner Point Removal [ CCL+23a , CCL+23b , CCL+24b ] , and many others. Despite much attention and effort, several fundamental questions regarding the size-distortion trade-off of tree covers remain unsolved, especially in the regime where k is as small as a constant. When k=1 , the best distortion is known to be \Theta(n) : the upper bound is achieved by the minimum spanning tree, and the lower bound is proved by the unweighted n -cycle [ RR98 ] . When k is a small constant, the best upper bound, due to Bartal, Fandina, and Neiman [ BFN22 ] , states that the stretch \tilde{O}(n^{1/k}) is achievable (actually by a more restricted type of tree covers, more discussion in Section 1.1 ). On the other hand, the best lower bound remains \Omega(\log_{k}n) , witnessed by high-girth graphs [ Bol04 ] , leaving a big gap. Closing this gap is viewed as one of the major interesting open problems on tree covers: • “Is there a better lower bound? Or perhaps there exists a tree cover with O(1) trees and distortion O(\log n) ? What can one say about a tree cover with only 2 trees?” – Bartal, Fandina, and Neiman in [ BFN22 ] . • “A very interesting open question: what is the smallest stretch achieved with 2 trees?’’ -- Le 1 1 1 at Sublinear Graph Simplification workshop at Simons Institute, video recording can be accessed at https://simons.berkeley.edu/talks/hung-le-university-massachusetts-amherst-2024-08-01 . 1.1 Our result In this paper, we make progress towards closing this gap. Our main result is the following theorem. Theorem 1 . For every k\geq 1 , there is an n -point metric, such that any size- k tree cover has stretch \Omega_{k}(n^{\frac{1}{2^{k-1}}}) . Specifically, when k=2 , our result implies a lower bound of \Omega(\sqrt{n}) , nearly matching the upper bound of \tilde{O}(\sqrt{n}) in [ BFN22 ] . For constant k , we show a polynomial lower bound, refuting the possibility of \mathrm{poly}\log n stretch. Therefore, Theorem 1 provides an answer to the above questions by Bartal, Fandina, Neiman, and Le. For proving Theorem 1 , we employ a novel approach. At a high-level, we construct a grid-like structure, compute its triangulation, label each point according to its location in the tree cover, and derive the stretch lower bound by Tucker’s Lemma. Our proof reveals a close connection between tree covers and the celebrated fixed-point theorems in combinatorial topology, and we believe that this connection will be useful in analyzing tree covers in different settings and other tree-like data structures. The stretch upper bound of \tilde{O}(n^{1/k}) in [ BFN22 ] is actually achieved by Ramsey tree covers, a restricted type of tree covers that require each vertex to choose a home tree to preserve its distances to all other vertices (formal definition in Section 5 ). They also showed a stretch lower bound of \Omega(n^{1/k}) for Ramsey tree covers. As a side result, we give an alternative proof of this near-optimal lower bound. Our hard instance is a high-dimensional cyclic grid, which is structurally simpler than the recursive construction in [ BFN22 ] . Our proof is similar to the proof of Theorem 1 and also makes use of a variant of Tucker’s Lemma. 2 Technical Overview In this section, we provide a high-level overview of our techniques, with the focus on the connection between tree covers and combinatorial topology. Case k=1 : examining a tree-based tour on a cycle We start by reviewing the proof of the \Omega(n) distortion lower bound for the case k=1 . We present a proof sketch similar to the one in [ RR98 ] , and an alternative proof can be found in [ Gup01 ] . Consider an unweighted cycle (0,1,2,\ldots,n-1,0) and a dominating tree T on the same set of vertices. We may assume without loss of generality that for each edge (i,j) in T (with i<j ), its length/weight is the cycle-distance between vertices i and j , namely \mathrm{dist}_{T}(i,j)=\min\left\{j-i,n-(j-i)\right\} , as otherwise we can decrease the length of this edge without hurting the distortion of T . To reveal the topological difference between a tree and a cycle, we “interpolate” their edges as follows. 1. For each edge (i,j) in T , we subdivide it by \mathrm{dist}_{T}(i,j)-1 new nodes (called interpolating nodes ), which are then labeled by consecutive integers connecting i,j in the natural order. For example, edge (3,6)\to(3,{\color[rgb]{1,0,0}4},{\color[rgb]{1,0,0}5},6) , and edge (1,n-3)\to(1,{\color[rgb]{1,0,0}0},{\color[rgb]{1,0,0}n-1},{\color[rgb]{1,0,0}n-2},n-3) . Edges (3,{\color[rgb]{1,0,0}4}),({\color[rgb]{1,0,0}4},{\color[rgb]{1,0,0}5})({\color[rgb]{1,0,0}5},6) are called interpolating edges . See Figure 1 for an illustration. 2. For each i , we define \Pi_{i} as the sequence of all nodes (including the old ones and the interpolating ones) we encounter while walking along the path from the old i to the old i+1 in T . Observe that the tree-distance between old nodes i,i+1 is |\Pi_{i}| , the number of interpolating edges in \Pi_{i} . Here \Pi_{n-1}