2025/11/09 by Agassy, Daniel, Dorfman, Dani, Kaplan, Haim
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.06574
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(log2 n loglog n), where n=|V|. This nearly matches the quality of the best known polynomial construction of a tree cut-sparsifier, of quality O(log1.5 n loglog 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(log3 n loglog 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(log4 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(log3 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(log2 n loglog n) tree cut-sparsifier.