Source-linked AI summary
A Nearly Optimal Min-Cut Algorithm for Dynamic Streams
Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
TL;DR
Dynamic-stream min-cut must handle arbitrary-order edge insertions and deletions, while directly sketching each vertex’s cut weight costs eO(n/ε²) space. We give an eO(n/ε)-space for-each cut sketch for weighted graphs under general turnstile updates and use it for min-cut. The resulting one-pass algorithm returns a (1+ε)-approximate minimum cut with high probability.
Problem
In arbitrary-order graph streams, the goal is to solve minimum cut using little space, while directly estimating the entire cut weight requires eO(n/ε²) space.
Source: §1 · p. 2, §1.2 · p. 6Method
An eO(n/ε)-space for-each cut sketch for weighted graphs under general turnstile updates is used in a one-pass minimum-cut algorithm.
Source: §1.1 · p. 3Results
The one-pass algorithm outputs a (1+ε)-approximate minimum cut with high probability using eO(n/ε) bits of space.
Source: §1.1 · p. 3Takeaways & Limitations
For every fixed k and p ∈ [1, ∞], the sketch also supports a (1+ε)-approximate minimum ℓp-norm k-partition using eO(n/ε) space.
Source: §1.1 · p. 5The construction is a cut sketch, and its techniques do not extend directly to preserving spectral information.
Source: §1.1 · p. 4
Abstract
from arXiv · showhide
We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pm\Delta$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.
1 Introduction
This section presents a one-pass approximate minimum-cut algorithm and a space-efficient for-each cut sketch for weighted turnstile streams, alongside extensions to fixed- k p -norm partitioning, two-cluster correlation-clustering evaluation, and balanced directed cut sketching. It also outlines the sketch’s technical approach and situates the results among prior streaming minimum-cut and graph-connectivity work.
1 Introduction
1.1 Our results
- One pass and eO(n/ε) bits suffice for a (1+ε)-approximate minimum cut under general weighted turnstile updates, matching the known Ω(n/ε) lower bound up to polylogarithmic factors.The update time is t + poly log n, where t is the update time of a constant-approximation for-all cut sparsifier.Source: §1.1 · pp. 3–4
- The core contribution is a one-pass eO(n/ε)-space for-each cut sketch for weighted general-turnstile streams, optimal up to polylogarithmic factors and simpler than prior decomposition-based approaches.It uses exact counters, ℓ1-samplers, and constant-dimensional Cauchy sketches, without high-expansion or short-cycle decompositions.Source: §1.1 · p. 4
- For every fixed k ≥2 and p ∈[1, ∞], one pass uses eO(n/ε) bits to approximate the minimum ℓp-norm k-partition under general turnstile updates with nonnegative final edge weights.The update time is t + poly log n, where t is the update time of a constant-approximation for-all cut sparsifier.Source: §1.1 · p. 5
- For any fixed two-clustering, disagreement cost can be estimated within (1 ± ε) using eO(n/ε) bits under general turnstile updates to nonnegative final positive and negative weights.This improves the prior eO(n/ε²)-space bound for arbitrary nonnegative weights.Source: §1.1 · p. 5
- For β-balanced weighted directed graphs with nonnegative final edge weights, the sketch gives a one-pass (1 ± ε) approximation for any fixed nontrivial cut using eO(n√β/ε) space.This matches the known for-each space bound up to logarithmic factors and is maintained under general turnstile updates.Source: §1.1 · p. 5
1.2 Technical Overview
- The technical overview reduces minimum cut to evaluating a polynomial-size family of candidate cuts, while its sketch estimates only the minority cut-edge mass after recovering positive-negative imbalance exactly.The bipartite representation assigns each edge a sign relative to the queried cut; a signed sum reveals imbalance, leaving the minority mass to estimate.Source: §1.2 · pp. 6–8
- A direct per-vertex linear ℓ1-sketch would use eO(n/ε²) space, so the overview instead exploits exact imbalance information to avoid estimating the entire cut weight.The direct method cancels internal edges and retains crossing edges, but needs eΘ(1/ε²) space per vertex for a (1±ε) estimate.Source: §1.2 · pp. 6, 8
- One repetition returns a (1 ± ε) approximation to the cut weight with constant probability; independent repetitions followed by taking the median amplify this guarantee to high probability.A cell has large variance only when it contains substantial weight from both positive and negative edges.Source: §1.2 · p. 9
- Product bucketing preserves B² cells while reducing storage from 2nB² vertex–cell pairs to 2nB vertex–bucket summaries, yielding Õ(n/ε) space.Each left vertex is assigned to one of B buckets and needs summaries only for the B right buckets; symmetrically, each right vertex needs B summaries for the left buckets.Source: §1.2 · p. 10
- Although product bucketing correlates edge locations and can concentrate weight in a few cells, distinct endpoints make each opposite-sign cut-edge pair share a cell with probability 1/B².Thus, the variance analysis retains the same bound by linearity of expectation, despite correlations between different edge pairs.Source: §1.2 · p. 10
1.3 Related Work
- Prior exact minimum-cut streaming algorithms use Õ(n) space with extra passes for simple unweighted graphs [RSW18] and weighted graphs [MN20], while random-order simple unweighted graphs admit a one-pass algorithm [DGL+25].For insertion-only approximate minimum cut, Cohen-Addad, Woodruff, Xie, and Zhou [CWXZ25] improved the logarithmic factors in the space bound of [DGL+25].Source: §1.3 · pp. 10–11
- Graph-stream research beyond minimum cut studies k-edge- and k-vertex-connectivity, including connectivity testing and sparse certificates [AS23] [GS24].For k = 1, Nelson and Yu [NY19] proved optimal space lower bounds for spanning forests in dynamic streams.Source: §1.3 · p. 11
2 Preliminaries
The preliminaries establish the weighted turnstile model, define cuts and their objectives, and review the sketching and probabilistic tools used in the paper.
2 Preliminaries
- Basic notation fixes logarithms to base 2, defines “with high probability” as probability 1 − 1/poly(n), and assumes ε ≥ 1/n without loss of generality.For smaller ε, the text says the whole weighted graph can be stored explicitly within eO(n/ε) bits.Source: §2 · p. 11
2.1 Streaming model
- The streaming model represents a weighted graph by edge weights updated by arbitrary integer increments, with nonnegative final weights and one-pass space measured in bits.The vertex set is fixed, and stream length and update magnitudes are bounded by poly(n).Source: §2.1 · p. 11
2.2 Cuts
- A cut separates a nonempty proper vertex subset from the rest; minimum cut and minimum k-cut minimize cut weight over cuts and k-partitions, respectively.The text also states the (1 + ε)-approximate objective for each problem.Source: §2.2 · pp. 11–12
2.3 ℓ1 samplers
- An ℓ1-sampler selects a coordinate with probability proportional to its absolute value, and the cited turnstile sketch uses eO(log^2 d log(1/δ)) bits.The analysis treats samplers as exact while absorbing their negligible distributional discrepancy into the failure probability.Source: §2.3 · p. 12
2.4 Cut Sparsifiers
- A for-all cut sparsifier approximates every cut simultaneously; a general weighted turnstile construction uses eO(n/ε^3) bits, or eO(n) for constant ε.The definition and guarantee apply to cuts of the final graph.Source: §2.4 · p. 12
2.5 L1 norm sketch via Cauchy random variables
- The paper uses Cauchy measurements and a decoder as an L1-norm estimator block, with finite-precision and pseudorandomness errors absorbed into the final guarantee.It takes r = 10 and states that a sufficiently large constant makes cumulative finite-precision error and failure probability negligible.Source: §2.5 · p. 13
2.6 Probabilistic Tools
- The preliminaries collect standard concentration inequalities, limited-independence hash functions, and a Chernoff–Hoeffding-type bound for limited independence.A k-wise independent family can be sampled and stored using the stated bound in Proposition 2.11.Source: §2.6 · pp. 13–14
3 Min-cut algorithm
The algorithm combines a for-each cut sketch with a small candidate family from a constant-accuracy for-all sparsifier to approximate minimum cut. Its sketch uses eO(n/ε) space under general turnstile updates.
3 Min-cut algorithm
- eO(n/ε) bits suffice for a one-pass (1 + ε)-approximate minimum cut algorithm on weighted undirected graphs under general turnstile updates.The algorithm succeeds with high probability.Source: §3 · p. 14
- For each vertex–bucket pair, the sketch keeps exact aggregate-weight counters, L1-norm estimator blocks, and L1-samplers.The counter families use 2nb counters; the blocks and samplers are maintained for both sides.Source: §3 · pp. 15–16
- A for-each cut sketch lets the algorithm estimate every cut in a polynomial-size candidate family containing an actual minimum cut.The family consists of small cuts identified using a constant-accuracy for-all sparsifier; a union bound supports simultaneous accuracy on the candidates.Source: §3 · pp. 14–15
- The for-each sketch estimates each fixed cut within (1 ± ε) with failure probability δ using eO((n/ε) log(1/δ)) bits.Its update time is eO(log(1/δ)).Source: §3 · p. 15
- The sketch represents each graph edge once in a bipartite graph, then hashes both vertex sides into b = 4/ε buckets.Each pair of buckets forms a cell.Source: §3 · p. 15
L1-samplers.
- The L1-samplers have polylogarithmic space, and with b = O(1/ε), the sampler structures use eO(n/ε) bits.The estimator blocks and samplers can be updated in polylogarithmic time.Source: §3 · p. 17, L1-samplers · p. 17
3.1 Analysis
- In each cell, the combined sampler vector is supported exactly on cut edges, with coordinate magnitude equal to edge weight and sign indicating edge direction across the cut.The estimator uses the sampled minority sign together with an L1-mass estimate to estimate the cell’s cut weight.Source: §3.1 · pp. 18–19
- Independent repetitions return a (1 ± ε)-approximation with probability at least 3/4 each; taking their median reduces failure probability to δ.The proof uses t = O(log(1/δ)) repetitions.Source: §3.1 · p. 21
4 ℓp-Norm k-Partitioning
The section extends the for-each cut sketch to minimum ℓp-norm k-partitioning for fixed k. A constant-accuracy sparsifier identifies polynomially many candidates, which the sketch evaluates to obtain a (1 + ε)-approximation in eO(n/ε) space.
4 ℓp-Norm k-Partitioning
- The algorithm uses a for-all sparsifier to identify polynomially many candidate partitions, then queries the for-each sketch on their parts and selects the smallest estimated objective.For fixed k, the candidate family has polynomial size, enabling a union bound over the queries.Source: §4 · pp. 21–22
- For fixed k and every p ∈ [1, ∞], a one-pass algorithm finds a (1 + ε)-approximate minimum ℓp-norm k-partition using eO(n/ε) bits.The input is a weighted undirected graph under general turnstile updates with nonnegative final edge weights.Source: §4 · p. 22
- An optimum ℓp-norm k-partition is a (k/2)-approximate minimum k-cut for every p ∈ [1, ∞].This makes the counting bound for approximate minimum k-cuts applicable to candidate generation.Source: §4 · pp. 21–22
- For p = 1, minimizing the ℓ1 objective gives the same partition as minimum k-cut, and half the objective value equals the ordinary k-cut value.Source: §4 · p. 24
- The space bound for estimating the optimum ℓp-norm value is optimal up to polylogarithmic factors for fixed k and p.The ordinary minimum-cut lower bound transfers by adjoining k − 2 isolated vertices.Source: §4 · p. 24
5 Two-cluster correlation clustering
For two-cluster correlation clustering, the disagreement cost can be represented as one cut query in an auxiliary graph. The for-each cut sketch then estimates the cost of any fixed clustering with eO(n/ε) space.
5 Two-cluster correlation clustering
- The disagreement cost equals the weight of a single cut in an auxiliary graph on two copies of the vertex set.Edges encode positive and negative constraints so that the cut weight matches the clustering’s disagreement cost.Source: §5 · pp. 24–25
- For two-cluster instances, the reduction imposes no probability constraints on positive and negative weights.Source: §5 · p. 24
- A fixed two-clustering’s disagreement cost is estimated within (1 ± ε) using eO(n/ε) bits and polylogarithmic update time.The guarantee holds under general turnstile updates when final positive and negative constraint weights are nonnegative.Source: §5 · p. 25
- With at most s nonzero negative constraints, the method extends to arbitrarily many clusters using eO(n/ε + s) bits, improving the eO(n/ε^2 + s)-space baseline.It estimates the positive-term contribution with at most n cut queries and recovers the negative-term contribution exactly.Source: §5 · p. 25
6 Balanced directed graphs
The section adapts the for-each cut sketch to estimate outgoing cut weight in balanced directed graphs. The resulting space is eO(n√β/ε), with polylogarithmic update time.
6 Balanced directed graphs
- The sketch distinguishes outgoing from incoming edges and uses β-balance to bound incoming weight by β times outgoing weight across the complementary cut.This balance condition underlies the eO(n√β/ε)-space bound.Source: §6 · pp. 25, 27
- For β-balanced weighted directed graphs, a for-each cut sketch estimates outgoing cut weight using eO(n√β/ε) bits and polylogarithmic worst-case update time.The guarantee applies under general turnstile updates when final edge weights are nonnegative.Source: §6 · p. 26
- The directed construction preserves endpoint order and uses left/right vertex copies, bucket hashes, counters, L1-norm estimators, and L1-samplers.Each ordered pair (u, v) is treated as a distinct coordinate.Source: §6 · p. 26
AI disclosure
The authors describe AI assistance in manuscript preparation and in developing parts of the technical results, while assuming responsibility for the content.
AI disclosure
- AI assistance was used to a limited extent for rewording, presentation, and figure design, and also contributed to part of the technical result.The authors state that subsequent algorithm development and analysis were carried out by them.Source: AI disclosure · p. 27
- In discussions with ChatGPT 5.6 Sol about candidate hard instances and counterexamples, the authors identified the algorithm’s bucketing idea.Source: AI disclosure · p. 27
- Gemini brainstorming contributed to identifying the ℓp-norm k-partitioning corollary; Sol identified and wrote the other two extensions.The authors assume responsibility for all content.Source: AI disclosure · p. 27
A Omitted proofs from preliminaries
The omitted proofs establish finite-precision estimator accuracy, couple the resulting sketches, and reduce randomness while retaining polylogarithmic update time.
A Omitted proofs from preliminaries
- With probability at least 1 − η/2, every finite-precision measurement differs from its ideal measurement by at most ε‖x‖₁.Source: A Omitted proofs from preliminaries · p. 34
- The finite-precision estimator and pseudorandom sketch states are coupled to their ideal or independent counterparts, yielding the claimed coupling guarantee.The proof bounds the two coupling failures by η each.Source: A Omitted proofs from preliminaries · p. 35
- Independent coefficient blocks can be replaced by pseudorandom blocks from an O(log^2(d/η))-bit seed, changing final-sketch event probabilities by at most η.A block can be regenerated for an updated coordinate in polylogarithmic time.Source: A Omitted proofs from preliminaries · p. 35