{"ID":2882179,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.10376","arxiv_id":"2508.10376","title":"Lower Bounds on Tree Covers","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.10376","url_pdf":"https://arxiv.org/pdf/2508.10376v2","authors":"[\"Yu Chen\",\"Zihan Tan\",\"Hangyu Xu\"]","published":"2025-08-14T06:11:37Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}