Harald Räcke

Gramoz Goranci, Monika Henzinger, Harald Räcke et al.

We give an algorithm that, with high probability, maintains a $(1-ε)$-approximate $s$-$t$ maximum flow in undirected, uncapacitated $n$-vertex graphs undergoing $m$ edge insertions in $\tilde{O}(m+ n F^*/ε)$ total update time, where $F^{*}$ is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ($m = Ω(n^2)$), and more generally, for graphs where $F^*= \tilde{O}(m/n)$. At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC '02, SICOMP '15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC '11, SICOMP '19] from undirected graphs to balanced directed graphs.

Kathrin Hanauer, Monika Henzinger, Robin Münk et al.

Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.