2026-09-08T02:22:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26396 2026-09-05T19:41:59Z ddc:004 open_access

Improved Tree Sparsifiers in Near-Linear Time Agassy, Daniel Dorfman, Dani Kaplan, Haim Tree sparsifiers cut sparsifiers flow sparsifiers congestion approximators expander decomposition near-linear time algorithms A 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 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² 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³ 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⁴ n). Our algorithm builds on a recent 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³ n). We then introduce a near-linear time 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² n log log n) tree cut-sparsifier. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Agassy and Dani Dorfman and Haim Kaplan 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.7 urn:nbn:de:0030-drops-263967 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode