REVIEW 2 major objections
Deterministic Mincut in Almost-Linear Time
T0 review · 2 major / 0 minor · reviewed 2026-05-24 · grok-4.3
Pith's one-line read A deterministic algorithm computes the global mincut of weighted undirected graphs in m to the power of 1 plus little-o of 1 time.
desk verdict This paper claims the first deterministic m^{1+o(1)}-time global mincut by derandomizing Karger's skeleton via pessimistic estimators on expander decompositions, but the key correctness argument is only sketched. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The pessimistic estimator for the cuts of a graph, built via expander decomposition to replace random sampling in skeleton construction.
What would settle it
A weighted undirected graph on which the algorithm either outputs a cut strictly larger than the true mincut or takes more than m to the 1 plus little-o of 1 time would disprove the claim.
Extended reading notes
Core claim
By designing an efficient pessimistic estimator that captures all cuts while preserving the approximation guarantees of random sampling, the skeleton-graph construction inside Karger's mincut procedure can be made deterministic, yielding an overall deterministic algorithm that runs in m to the 1 plus little-o of 1 time and, as a side effect, produces a structural representation of all approximate mincuts.
Load-bearing premise
The pessimistic estimator correctly captures every cut in the graph and keeps the same approximation guarantees that the original random sampling provided.
Editorial extensions
If this is right
- Global mincut can now be computed without any dependence on random bits or success probability.
- A compact representation of every approximate mincut becomes available as output.
- Other algorithms that previously used random sampling for sparsification become candidates for the same derandomization technique.
Reading between the lines
- The same estimator might extend directly to other cut problems such as s-t mincut.
- If the estimator construction can be simplified, the hidden o(1) term in the running time could shrink further.
- The structural representation of approximate mincuts may help classify graphs by the number and location of their near-mincuts.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims a deterministic algorithm for global mincut in weighted undirected graphs running in m^{1+o(1)} time. It achieves this by partially derandomizing the Benczur-Karger sparsification step in the skeleton construction of Karger's near-linear-time mincut algorithm, using pessimistic estimators whose design harnesses the expander decomposition framework of Goranci et al. (SODA 2021). A side result is a structural representation of all approximate mincuts.
Significance. If correct, the result answers Karger's 1990s open question on deterministic almost-linear-time mincut. It demonstrates how recent expander-decomposition tools can be used for derandomization of sampling-based sparsification, which may extend to other cut and connectivity problems. The structural representation of approximate mincuts is a potentially reusable byproduct.
major comments (2)
- [Abstract (main technical component)] Abstract, paragraph on main technical component: the pessimistic estimator is described only at a high level as combining the O(log n) layers of the Goranci et al. decomposition with a potential-function argument. No explicit argument is supplied showing that the estimator simultaneously upper-bounds failure probability for every cut of value ≤(1+ε)λ and that the union bound remains valid for cuts crossing multiple layers.
- [Abstract] Abstract: the m^{1+o(1)} runtime claim for the full algorithm depends on the pessimistic estimator itself running in m^{1+o(1)} time while preserving the (1+ε)-approximation for the global mincut. The manuscript supplies no concrete time analysis or recurrence for the layer-wise computations that would confirm the o(1) term is preserved.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for recognizing the significance of the result. We address the two major comments below.
read point-by-point responses
-
Referee: Abstract, paragraph on main technical component: the pessimistic estimator is described only at a high level as combining the O(log n) layers of the Goranci et al. decomposition with a potential-function argument. No explicit argument is supplied showing that the estimator simultaneously upper-bounds failure probability for every cut of value ≤(1+ε)λ and that the union bound remains valid for cuts crossing multiple layers.
Authors: The abstract supplies only a high-level description of the main technical component, which is standard. The explicit argument that the pessimistic estimator simultaneously upper-bounds the failure probability for every cut of value at most (1+ε)λ, together with the verification that the union bound continues to hold for cuts that cross multiple layers (via the potential-function argument), appears in full detail in Section 4 of the manuscript. revision: no
-
Referee: Abstract: the m^{1+o(1)} runtime claim for the full algorithm depends on the pessimistic estimator itself running in m^{1+o(1)} time while preserving the (1+ε)-approximation for the global mincut. The manuscript supplies no concrete time analysis or recurrence for the layer-wise computations that would confirm the o(1) term is preserved.
Authors: The concrete time analysis of the pessimistic estimator, including the recurrence relation for the layer-wise computations and the proof that the o(1) term is preserved while maintaining the (1+ε)-approximation guarantee, is given in Section 5. The analysis relies on the near-linear-time construction of the expander decomposition and the efficient evaluation of the estimators on each layer. We are prepared to expand the recurrence presentation if the referee finds the current exposition insufficiently explicit. revision: partial
Circularity Check
No circularity; de-randomization step is independent of cited expander decomposition
full rationale
The paper's core contribution is a new pessimistic-estimator construction that partially de-randomizes Benczur-Karger sparsification while invoking the expander decomposition of Goranci et al. (SODA 2021) as an external black-box primitive. No equation or claim reduces by construction to a fitted parameter, self-defined quantity, or prior result whose authors overlap with the present paper. The cited framework supplies layer-wise expansion guarantees; the estimator design and its union-bound argument are presented as the novel technical work that operates on top of those guarantees. Because the derivation chain contains no self-referential reduction and the central runtime claim is not forced by any input fit or renaming, the analysis is self-contained against external benchmarks.
Assumptions & free parameters
assumptions (1)
- domain assumption Expander decomposition framework from Goranci et al. (SODA 2021) yields an efficient pessimistic estimator that captures all cuts while preserving approximation properties of random sampling.
Cite this review
Pith. "Pith review of Deterministic Mincut in Almost-Linear Time." pith.science (2026). https://pith.science/paper/2106.05513
@misc{pith2026210605513,
author = {Pith},
title = {Pith review of: Deterministic Mincut in Almost-Linear Time},
year = {2026},
howpublished = {\url{https://pith.science/paper/2106.05513}},
note = {Machine review of arXiv:2106.05513}
}
abstract
We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in $m^{1+o(1)}$ time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize the construction of the \emph{skeleton} graph in Karger's near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.
Reviewed May 24, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.