# Directed Global Minimum Cut in Almost-Linear Time

Preprint · Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang

- Archive id: arxiv:2610.10898
- Published: 2026-10-07
- arXiv: https://arxiv.org/abs/2610.10898
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.10898
- PDF: https://arxiv.org/pdf/2610.10898
- Provenance: arxiv

## Abstract

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 the previous $m^{1+o(1)}\\min\\{\\sqrt{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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.