Preprint
Oct 2026
Directed Global Minimum Cut in Almost-Linear Time
We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving th...
Henry L. Fleischmann, Jason Li, Thatchaphol Saranurak et al.
· 1 citation