{"ID":2844489,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06574","arxiv_id":"2511.06574","title":"Improved Tree Sparsifiers in Near-Linear Time","abstract":"A \\emph{tree cut-sparsifier} $T$ of quality $α$ of a graph $G$ is a single tree that preserves the capacities of all cuts in the graph up to a factor of $α$. A \\emph{tree flow-sparsifier} $T$ of quality $α$ guarantees that every demand that can be routed in $T$ can also be routed in $G$ with congestion at most $α$. We present a near-linear time algorithm that, for any undirected capacitated graph $G=(V,E,c)$, constructs a tree cut-sparsifier $T$ of quality $O(\\log^{2} n \\log\\log n)$, where $n=|V|$. This nearly matches the quality of the best known polynomial construction of a tree cut-sparsifier, of quality $O(\\log^{1.5} n \\log\\log n)$ [Räcke and Shah, ESA~2014]. By the flow-cut gap, our result yields a tree flow-sparsifier (and congestion-approximator) of quality $O(\\log^{3} n \\log\\log n)$. This improves on the celebrated result of [Räcke, Shah, and Täubig, SODA~2014] (RST) that gave a near-linear time construction of a tree flow-sparsifier of quality $O(\\log^{4} n)$. Our algorithm builds on a recent \\emph{expander decomposition} algorithm by [Agassy, Dorfman, and Kaplan, ICALP~2023], which we use as a black box to obtain a clean and modular foundation for tree cut-sparsifiers. This yields an improved and simplified version of the RST construction for cut-sparsifiers with quality $O(\\log^{3} n)$. We then introduce a near-linear time \\emph{refinement phase} that controls the load accumulated on boundary edges of the sub-clusters across the levels of the tree. Combining the improved framework with this refinement phase leads to our final $O(\\log^{2} n \\log\\log n)$ tree cut-sparsifier.","short_abstract":"A \\emph{tree cut-sparsifier} $T$ of quality $α$ of a graph $G$ is a single tree that preserves the capacities of all cuts in the graph up to a factor of $α$. A \\emph{tree flow-sparsifier} $T$ of quality $α$ guarantees that every demand that can be routed in $T$ can also be routed in $G$ with congestion at most $α$. We...","url_abs":"https://arxiv.org/abs/2511.06574","url_pdf":"https://arxiv.org/pdf/2511.06574v2","authors":"[\"Daniel Agassy\",\"Dani Dorfman\",\"Haim Kaplan\"]","published":"2025-11-09T23:34:38Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}