Directed Global Minimum Cut in Almost-Linear Time
In the authors' words
We give a randomized reduction from global minimum cut in a directed graph with vertices and weighted edges to maximum-flow computations on graphs of total size . For polynomially bounded integral weights, this yields the first almost-linear -time algorithm [vdBCK+23], improving the previous 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 -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 rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.
Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 11 pages, 4 figures