arXiv preprint ·
Directed Global Minimum Cut in Almost-Linear Time
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Envy-free Allocations with Individual Payments
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.