arXiv · Oct 7, 2026
Directed Global Minimum Cut in Almost-Linear Time
By Henry Fleischmann, Jason Li, Thatchaphol Saranurak et al.
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 O(m). For polynomially bounded integral weights, this yields the first almost-linear m^(1+o(1))-time algorithm [vdBCK+23], improving the previous m^(1+o(1))min{√n,n/m^(1/3)} bound [CLN+22]. Previous work reduced finding the minimum cut to constructing a 1-respecting arborescence, a directed spanning tree with exactly one edge crossing a minimum cut [CLN+22]. They then construct such a tree by sampling from a (1+ε)-approximate arborescence packing, which currently requires superlinear time. Our algorithm sidesteps constructing the packing entirely and relies on a novel iterative arborescence sampling procedure. We show that, after O(log n) rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.