Improved Tree Sparsifiers in Near-Linear Time

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"acke 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"acke, Shah, and T"aubig, 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.