pipette
ENEnglish

Directed Global Minimum Cut in Almost-Linear Time

Henry Fleischmann, Jason Li, Thatchaphol Saranurak, and Benyu Wang

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 11 pages, 4 figures