{"ID":2854780,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.14918","arxiv_id":"2510.14918","title":"Tree-Like Shortcuttings of Trees","abstract":"Sparse shortcuttings of trees -- equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter -- have been studied extensively (under different names and settings), since the pioneering works of [Yao82, Cha87, AS87, BTS94], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Yao82, Cha87, AS87, BTS94] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for $n$-node trees with sparsity $O(\\log^* n)$. Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity $Ω(\\log n)$), which is a significant drawback for many applications. We initiate a systematic study of constant-hop tree shortcuttings that are ``tree-like''. We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold. * New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to $O(\\log\\log n)$. We also provide a lower bound for larger values of $k$, which together yield $\\text{hop-diameter}\\times \\text{treewidth} = Ω((\\log\\log n)^2)$ for all values of hop-diameter, resolving an open question of [FL22, Le23]. [...]","short_abstract":"Sparse shortcuttings of trees -- equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter -- have been studied extensively (under different names and settings), since the pioneering works of [Yao82, Cha87, AS87, BTS94], initially motivated by applications to range queries, online tree product, and MST...","url_abs":"https://arxiv.org/abs/2510.14918","url_pdf":"https://arxiv.org/pdf/2510.14918v2","authors":"[\"Hung Le\",\"Lazar Milenković\",\"Shay Solomon\",\"Cuong Than\"]","published":"2025-10-16T17:34:55Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}