Source-linked AI summary
Directed Global Minimum Cut in Almost-Linear Time
Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang
TL;DR
Exact directed minimum cut had lacked an almost-linear-time algorithm, despite prior faster-than-naive approaches. This paper reduces it to maximum-flow computations and uses iterative arborescence sampling; with high probability, the reduction computes a mincut using total graph size eO(m).
Problem
An almost-linear-time exact algorithm for directed minimum cut remained open, following a previous general weighted-graph bound of m^1+o(1) min{√n, n/m^1/3}.
Source: §1 · p. 1Method
The paper gives a near-linear-size maximum-flow reduction built around iterative sampling and updating of a random arborescence.
Source: §1 · pp. 1–2, §2 · p. 2Results
With high probability, directed minimum cut uses maximum-flow computations on graphs of total size eO(m), with eO(m) additional time, yielding m^1+o(1) time with almost-linear maximum flow [vdBCK+23].
Source: §1 · p. 1Takeaways & Limitations
The result also gives the first almost-linear-time algorithms for second (s,t)-mincut and arboricity value.
Source: §1 · p. 2A stronger bound for Lemma 2.2 is conditional on proving h(δ−(S)) ≥ 1 for every nonempty root-excluding set S.
Source: §4.2 · p. 6
Abstract
from arXiv · showhide
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+\epsilon)$-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.
1 Introduction
Almost-linear-time exact directed minimum cut had remained open despite prior algorithms, including a slower bound for general weighted graphs. This work reduces the problem to maximum flow and gives an almost-linear algorithm under polynomially bounded integral weights.
1 Introduction
- The previous fastest general weighted-graph algorithm ran in m^1+o(1) min{√n, n/m^1/3} time.Almost-linear-time exact algorithms had remained open.Source: §1 · p. 1
- The algorithm assumes positive integral edge weights bounded by W, with m and W polynomial in n.These are the stated input conditions for the near-linear-size reduction.Source: §1 · p. 1
- With high probability, directed minimum cut reduces to maximum-flow computations on graphs of total size eO(m), with eO(m) additional time.Using almost-linear-time maximum flow [vdBCK+23], the resulting algorithm runs in m^1+o(1) time.Source: §1 · p. 1
- The result also gives the first almost-linear-time algorithms for second (s,t)-mincut and the value of arboricity.The cited reductions use linear-total-size instances.Source: §1 · p. 2
- Its key technique updates a random arborescence until it crosses the mincut only once with constant probability.This suffices to obtain a mincut through a known reduction.Source: §1 · p. 2
2 Mincut via Iterative Arborescence Sampling
Iterative arborescence sampling yields a tree that 1-respects a rooted minimum cut with probability greater than 1/2, and independent repetition gives high-probability cut recovery. This avoids constructing an approximate arborescence packing, which prior approaches require.
2 Mincut via Iterative Arborescence Sampling
- Finding an arborescence that 1-respects a rooted cut suffices: every arborescence crosses each rooted cut at least once, and cut recovery returns a rooted mincut when the tree 1-respects one.A rooted cut is a nonempty vertex set excluding the root; the rooted mincut minimizes incoming edge weight.Source: §2 · p. 2
- Prior approaches sampled once from an approximate arborescence packing, but direct construction took eO(mλ) time and almost-linear packing had insufficiently small congestion.An almost-linear-time algorithm for exact or (1 + ε)-approximate fractional arborescence packing remains an open problem.Source: §2 · p. 2
- Iterative sampling improves one random tree’s marginals: each update halves the excess of its inclusion probabilities above q, without computing the feasible point dominated by q.The marginal-contraction update uses one maximum-flow computation on an eO(m)-size graph and eO(m) additional time.Source: §2 · p. 2
- A rooted-cut approximation provides C with λ ≤ C ≤ 5λ/4; setting L = 4C/5 gives L ≤ λ < 4L/3, and Edmonds’ theorem supplies packing marginals bounded by q.The average of λ edge-disjoint arborescences has edge marginals x_e ≤ w_e/λ ≤ q(e).Source: §2 · p. 3
- With probability greater than 1/2, the final tree 1-respects the rooted minimum cut; O(log n) independent repetitions and cut recovery find a rooted mincut with high probability.Sampling and recovery use O(log^2 n) maximum-flow computations on eO(m)-size graphs and eO(m) additional time.Source: §2 · p. 3
3 Implementing the Marginal Contraction
The marginal-contraction implementation uses a randomized integral flow to augment an arborescence, then decomposes the resulting multigraph into two edge-disjoint arborescences and samples one. The flow construction uses one maximum-flow call on an eO(m)-size graph, plus eO(m) additional time.
3 Implementing the Marginal Contraction
- A randomized integral flow f ensures every rooted cut has at least two incoming edges in the augmented multigraph 1_T + f.The flow algorithm uses one maximum-flow call on an eO(m)-size graph, plus eO(m) additional time.Source: §3 · p. 3
- Edmonds’ packing theorem implies the augmented graph contains two edge-disjoint r-arborescences; because it has exactly 2n −2 multi-edges, it is their union.Tarjan’s algorithm computes two edge-disjoint arborescences in O(|E| log |E|) time when they exist.Source: §3 · pp. 3–4
- Standard binary search can replace Quanrud’s algorithm to find C satisfying λ ≤ C ≤ 5λ/4.The footnote gives this as an alternative for obtaining the approximation used to set L.Source: §3 · p. 3
- The sampling algorithm decomposes 1_T + f into two edge-disjoint r-arborescences, then returns one chosen uniformly at random.The flow subroutine is the key assumption for this implementation of marginal contraction.Source: §3 · pp. 3–4
4 Support Mixing Flow Subroutine
The support-mixing subroutine uses an arborescence T and q dominating a point x in Ar to construct an integral flow with rooted cut-connectivity two. It requires one max-flow call on an eO(m)-size graph and eO(m) additional time.
4 Support Mixing Flow Subroutine
4.1 Flow Network Construction: Warmup
- The warmup network limits original-edge flow by q(e) and routes it to tree-edge sinks along fundamental-cycle paths, representing fractional swaps of tree edges.For an edge e, each tree edge on its path P_T(e) is a possible replacement in the network.Source: §4.1 · pp. 5–6
4.2 Demand-Satisfying Flows are Good
- Any demand-satisfying auxiliary flow yields rooted cut-connectivity two: if T crosses a set only once, the projected flow contributes at least one incoming unit.If T crosses the set at least twice, T alone supplies the required connectivity.Source: §4.2 · p. 6
4.3 Feasible Solutions Exist
- When q dominates an arborescence-packing point, a feasible demand-routing flow exists by expressing that point as a convex combination of arborescences.For each arborescence, a perfect matching between its edges and T's edge sinks gives the corresponding flow; Hall's condition follows from the crossing edges between components of T after deleting a set of tree edges.Source: §4.3 · p. 7
4.4 Final Compressed Network Flow Construction and Flow Rounding
- Heavy-light decomposition and segment trees compress the auxiliary network while preserving which tree-edge sinks each original edge can reach.The construction adds O(log^2 n) edges per original edge and yields a network with O(m+n) nodes and O(m log^2 n) edges.Source: §4.4 · pp. 7–8
- Randomized flow rounding produces an integral demand-satisfying flow, and the rooted cut-connectivity condition still holds without enforcing the capacity bounds on the rounded flow.The rounded projection therefore satisfies the conditions of Lemma 3.1.Source: §4.4 · p. 10