Faster Global Minimum Cut with Predictions
Authors: Helia Niaparast
Benjamin Moseley
Karan Singh
Venue: ICML 2025 poster (2025)
Keywords: Algorithms with Predictions
Minimum Cut
Karger
Karger-Stein
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We incorporate predictions into Karger and Karger-Stein algorithms to develop faster methods for finding the global minimum cut.

Abstract: Global minimum cut is a fundamental combinatorial optimization problem with wide-ranging applications. Often in practice, these problems are solved repeatedly on families of similar or related instances. However, the de facto algorithmic approach is to solve each instance of the problem from scratch discarding information from prior instances.  

In this paper, we consider how predictions informed by prior instances can be used to warm-start practical minimum cut algorithms. The paper considers the widely used Karger's algorithm and its counterpart, the Karger-Stein algorithm. Given good predictions, we show these algorithms become near-linear time and have robust performance to erroneous predictions.  Both of these algorithms are randomized edge-contraction algorithms. Our natural idea is to probabilistically prioritize the contraction of edges that are unlikely to be in the minimum cut.

Faster Global Minimum Cut with Predictions
Helia Niaparast Benjamin Moseley Karan Singh
Abstract
chine learning naturally suited to this setting. Lykouris & Vassilvitskii (2021) provide a theoretical framework that characterizes the competitive ratio of algorithms based on the quality of machine-learned predictions. Subsequent re- search has applied this model to achieve higher-qualin so- lutions and break worst-case lower bounds in various prob- lems, including caching (Im et al. 2022 Lykouris & Vassil-
Global minimum cut is fundamental combi- natorial optimization problem with wide-ranging applications. Often in practice, these problems are solved repeatedly on families of similar or related instances. However, the de facto algo- rithmic approach is to solve each instance of the problem from scratch discarding information from prior instances.
vitskii 2021), binary search (Dinitz et al. 2024). schedul-
ing (Lindermayr & Megow] 2022 Lattanzi et al. 2020 Im
et 2023), and clustering (Lattanzi et al. 2021 For
In this paper, we consider how predictions in- formed by prior instances can be used to warm- start practical minimum cut algorithms. The paper considers the widely used Karger's al- gorithm and its counterpart, the Karger-Stein algorithm. Given good predictions, we show these algorithms become near-linear time and have robust performance to erroneous predic- tions. Both of these algorithms are randomized edge-contraction algorithms. Our natural idea is to probabilistically prioritize the contraction of edges that are unlikely to be in the minimum cut.
comprehensive overview, see the survey by Mitzenmacher & Vassilvitskii (2022).
Interestingly, the work of Kraska et al. 2018). which ar- guably initiated this line of work, had a different goal in mind and emphasized improvements in running time, a di- rection that remains underexplored compared advance- ments in solution quality. Their empirical results highlight the significant potential of machine learning to accelerate algorithms and motivate exploration of the algorithmic pos- sibilities of using machine learning for runtime improve- ments.
Traditionally, computer science solves problems from scratch, with running times analyzed using worst-case sce- narios. However, in practice, many problems repeat- edly solved over time. The conventional worst-case model often discards valuable information shared between in- stances. Given that problem instances frequently exhibit similaritics, machine learning offers an opportunity to learn warm-stare starting state that can enhance algorithmic perfor- mance. The community has begun investigate theoretical guarantees for algorithms that machine-learned warm starts to achieve runtime improvements, Dinitz et al. (2021) initiated this line of inquiry by showing how predicted dual variables could accelerate the Hungarian algorithm for bi- partite matching. Building on this idea, researchers have developed runtime-improving algorithms for discrete com- binatorial optimization problems, such shortest paths (Chen et al. 2022 McCauley et al., 2025), maximum flow (Davies al. 2023), list labeling data structures (Mc- 2024b). and dynamic graph algorithms (Mc-
1. Introduction
Machine learning is driving scientific breakthroughs. While this has transformed many areas, there remain do- mains where machine learning holds immense, yet unreal- ized potential. One such area is the reimagining of com- puter science foundations through machine learning, par- ticularly for designing faster discrete algorithms.
A rapidly growing body of work, collectively referred to as algorithms with predictions, focuses on leveraging machine-learned predictions to overcome worst-case per- formance barriers. In recent years, hundreds of papers have explored this model, mainly applying improve quality of solutions produced by online algorithms. The primary challenge in the online setting is uncertainty. Hence, ma-
'Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA. Correspondence to: Helia Niaparast <hnia- para@ aan.ddddr...c.ccdu..
Cauley et al.
Cauley et al. 2024a)
Despite these advances, this area remains underdeveloped, with significant open questions regarding how machine- learned predictions improve algorithmic runtimes.
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Faster Global Minimum Cut with Predictions
Global Minimum Cut. This paper focuses on the global minimum eut problem. Consider an undirected graph G (V, E, w) with vertex set V and edge set E, where each edge has a nonnegative weight w(e). We will use m to denote the number of edges and n. to denote the number of vertices, For an edge subset E" C E, let (") be the sum of weights of edges in E", and for a subset V S V of ver- tices, let 8(V") be the edges between V" and V \ V'. The goal is to find partition TS) of the vertex set that mini- mizes w (((())) = LEEEn(SXT) w(e), thus minimizing the total weight of the edges that cross the partition. Occa- sionally, we will refer to the minimum cut by the edges it contains, rather than by the partition that induces it.
at least ((1/n²). Therefore, by repeating Karger's algo- rithm Onn²) times and retaining the best cut across all runs, the algorithm recovers the true minimum cut with constant probability. Each run of Karger's algorithm can be per- formed in O(m) time; thus the total runtime is ((mn²). Karger's algorithm is known for its high parallelizabil- ity, making it appealing for large-scale distributed settings, Given sufficient number of parallel processors, each of these runs can be performed in parallel in O(m) time with zero intermittent communication. We will see that this also holds for the boosted variant of Karger's that we study.
The Karger-Stein algorithm considerably boosts the proba- bility of obtaining the minimum cut in any given trial to (11 log n) at the cost of On log n) runtime per trial, The key observation is that the probability that the min- imum cut survives random edge contraction decreases severely the fewer vertices there are left. Therefore, re- peated contractions when there are too many vertices re- maining as in Karger's algorithm are wasteful. Instead, starting with n vertices, Karger-Steie contracts edges at random until there are about n/V2 vertices left, and then returns the better of the cuts received by making two in- dependent recursive calls on the resultant graph. The net runtime of On log" n) is nearly optimal for dense graphs.
This problem has been extensively studied in the literature
Gomory & Hu 1961
Hao & Orlin 1994 Stoer & Wag-
ner
1997:
Karger 1993;
Karger& & Stein 1996
Karger
2000
Gabow
1995
Kawarabayashi & Thorup 201 8: Hen-
Zinger et al. 2020,
Saranurak 2021| Li & Panigrahi 2020:
Li
2021| Henzinger et al. 2024 Chekuri et al., 1997).
and has wide-reaching applications. c.g., network design and network reliability (Colbourn) 1987). information re- trieval (Botafogo 1993), and compiler design for paral- lel languages (Chatterjee et al., [995]. Following se- quence of breakthrough results, the fastest known algo- rithms for this problem run in near-linear (m poly log m) time, even when constrained to be deterministic (Henzinger ct al. 2024). However, known near-linear time algorithms are primarily of theoretical interest and often involve over- heads that limit their usability in practice. To our knowl- edge, these algorithms have not been implemented. In fact, popular graph libraries (Sick et al. 2001 Hagberg et al. 2008) resort to algorithms that are much slower in theory but easier to implement.
The natural questions we ask are: How can Karger's 's al- gorithm and the Karger-Stein algorithm be improved us- ing predictions? How error-resilient are the resultant prediction-uummented algorithms? What is the right mea- sure of error in such predictions?
1.1. Results
This paper improves the runtime performance of Karger's algorithm and the Karger-Stein algorithm using predic- tions. The first key question is: what should be predicted? The idea is to predict which edges are more less likely to be in the global minimum cut. Of course, these predictions could be erroneous. algorithms that robustly use these predictions.
Karger's 's and Ktrger-Stein Algorithms. Karger's 's algo- rithm (Karger 1993) and its extension, the Karger-Stein al- gorithm (Karger& & Stein 1996), are two renowned random- ized algorithms for finding the global minimum cut. They are frequently used as algorithmic benchmarks (Chekuri let al. 1997). The practical relevance of Karger's 's algorithm draws from its simplicity and its highly parallelizable na- ture. Given an unweighted graph G = E), at each iteration, Karger's algorithm picks an edge E E uni- formly at random and contracts its endpoints, keeping par- allel edges but removing self-loops. Once there are only two vertices left, the partition of the vertex set formed by these two "metavertices" is returned as a candidate for the minimum cut. This algorithm can be easily extended to weighted graphs, where an edge is picked with probabil- ity w((e)/ (w)E., and instead of adding parallel edges, the edge weights are summed upon contraction.
We introduce new variants of these
Predictions. Let C* C E be a minimum eut in G. Since cut ultimately is a subset of edges that cross some parti- tion of the set of vertices, let us begin by considering binary predictions for each edge e E E indicating whether or not e E C*. Let θ S E be the predicted minimum cut. Note that C may not necessarily be a cut.
Clearly, any edge in the symmetric set-difference ČΔC" constitutes an error. The majority of error measures con- sidered in the algorithms with predictions literature are symmetric (c.g.. in Mitzenmacher & Vassilvitskii (2022); Dinitz et al.] 2)21)); they penalize equally for over- and under- prediction. However, an important feature of our work to disentangle the impact of these two types of er-
can be shown that the cut reported by Karger's algorithm is actually a minimum cut of the graph with probability
2

---

Faster Global Minimum Cut with Predictions
rors on the algorithm's 's runtime. Concretely, the prediction error can be divided into false negatives (1)) and false posi- tives (p). We define 77 as the ratio of the weight of the edges in the minimum cut but not in the prediction to the weight of the minimum cut and as the ratio of the weight of the edges in the prediction but not in the minimum cut to the weight of the minimum cut:
Boosted Karger's algorithm (Algorithm oulputs a min-
imum cut with probability at least
Ω
2 p2(2))))))
Let us compare this to the (21/n²²) probability of recov- ering the true minimum eut in the standard Karger's algo- rithm. Regardless of the value of n, which is always in [0, 1J. the result in Theorem 1.1 is better than Karger's al- gorithm long as p S o(n). Thus, the result shows re- markable resiliency to error: Even if none of the minimum cut edges is in the prediction, and the predicted edges are almost n times as many as the minimum cut, the probability of recovering the minimum cut is no worse than Karger's algorithm.
w((( C*) 7: w(C+)= p: w(C+)
(0) (0)
1c(C"
We will see that false negative is far more costly than false positive in boosting the runtime of Karger-like algo- rithms.
In fact, we prove and state our results in a more general set- ting that cleanly generalizes the above definitions to real- valued predictions. Here, each edge e has an associated prediction Pe [0. representing the probabilistic pre- diction of its inclusion in C*, Now, y) and are defined as:
To see the utility of this result, consider when the error is small, c.g. if p is constant, then the probability of success of Boosted Karger's algorithm is Ω (1/n²*), which is sig- nificantly better than that of Karger's algorithm, Z (1/n²).
Elec. (1 - -Pa)w(e) p:= EeEEro- Powle) w(C*))
Boosting the Karger-Stein Algorithm. For Karger- Stein, it is important first to carve out the possible regime of improvement. For dense graphs, that is, if m = O(n²), Karger-Stein is already nearly optimal. For sparse graphs, the best one may hope for is a near-linear runtime of (()). Therefore, depending on the quality of the predictions, one may hope to interpolate these. This is what our results de- liver.
w((C))
In the analysis, we will only use that 7 and p are valid upper bounds for the quantities defined above, and, for simplicity, we assume that p is at least 1. We note that if there is more than one global minimum cut, 1 and can be defined with respect to any fixed minimum cut. Due to this, our runtime guarantees hold with respect to the minimum cut that gives the best runtime in terms of 1 and p.
As we will see, our earlier result relied on improving the minimum cut's probability of surviving a single random edge contraction. The Karger-Stein analysis is not directly well suited to make use of this effect. Instead, we adapt a variant, here eponymously termed FPZ, introduced in Fox et al. (2019), who obtain Sarger-Stein--ttlee guarantees for finding minimum cuts in hypergraphs. Their analysis was greatly simplified recently by Karger & Williamson (202T), which we borrow. The difference in FPZ vs. Karger-Stein is that the former executes single edge-contraction in each step. but makes random number of recursive calls; the propensity of these is closely tied to the survival probability of a minimum cut during edge contraction. Here, in ad- dition to tweaking the graph so that random edge contrac- tions are more likely to contract edges outside the predicted set, we modify the propensity for these recursive calls. In the end, we prove the following.
Boosted Karger's Algorithm. Our intuitive approach to taking advantage of predictions is to tweak the graph that Karger's algorithm has higher chance of contracting the edges that are not predicted to be in the minimum cut, so that the minimum cut has a higher chance of surviving.
A reasonable guess a priori is that the amount of compu- tational work needed to compute the minimum cut (and hence, the runtime) scales linearly in the quality of predic- tions, e.g. knowing about half of the edges in the minimum cut (given no false positives) reduces the total work by factor of half. However, we show that the improvement is far more stark, and such predictions can eliminate an entire factor of n from the runtime. Thus, even for fixed predic- tion quality, the multiplicative speed-up up grows with the size of instance.
Theorem 1.2. For a suitable setting of parameters, given predictions measured by 1) and p as defined above, the Boosted FPZ algorithm runs in time
We prove the following theorem, demonstrating the po- tential for significant improvement in the running time of Karger's algorithm, provided that the predictions are not too erroncous.
10m (mm--"n?? log 0(02(10)))2 logn) otherwise.
p O(/m), and
Theorem 1.1. For a suitable setting of parameters. given predictions measured by dj and p as defined above, the
It outputs a minimum cut with probability at least 52 log
3

---

Faster Global Minimum Cut with Predictions
For large and forgiving regime of false positives, when
Algorithm 1 Boosted Karger's 's Algorithm
P O(ym), the running time multiplicatively interpo-
1: Input: graph G = (V, E, w), predictions {pe JeEE.
lates that of Karger-Stein and a near-linear time algorithm, depending on the value of 1). For small 17, is almost linear- time. In fact, the improvement over Karger-Stein persists regardless of the value of 17 as long as S o(n).
2: Parameters: scaling factor B, threshold t.
Let (F(()) = (1 (B 1)(1 pe))u((e) and build the graph GB (V, E, wB).
4: while there are vertices left in G. do
5: Pick an edge ě with probability x wB(e). that is,
We note that our running-time analysis, along with the underlying data structures supporting the implementation. differs from prior work. Importantly, our recurrence anal- ysis is careful as to how many edges are processed in each iteration, effectively amortizing the total work done across multiple levels of recursion.
with wg (e)/eEE((n)) WB(C), and contract it.
6: end while
7: Define G' = (V',
:= subgraph of G induced by the remaining metavertices in GB.
while there are at least 3 vertices left in G' do Pick edge with probability w(e). that is, with w(ē)/ ZEEB(G)) w(e). and contract it. 10: end while
Learning Near-Optimal Predictions. We also give a learning algorithm to learn near-optimal predictions from solutions to past instances. Specifically, given a distribu- tion over graphs, from which the learning algorithm can draw samples, we show how near-optimal predictions min- imizing average runtime over the distribution may be com- puted in polynomial time and sample complexity.
11: return the set of edges in G between the two remaining metavertices.
the first phase, and the execution of the standard Karger's s algorithm on lines 7-10 as the second phase. For brevity of notation, we define the sequence
Experiments. We conduct three sets of experiments ranging from synthetic to real datasets.
1 (B 1)m q: 1 B - - (1-++(1-)))
Limitations. One limitation of our approach is that the setting of the parameters needed for the theoretical results depends on the knowledge of and p (or at least on up- per bounds for them). Given family of instances, it might be possible to conservatively estimate these parameters, but we do not pursue this here. However, in our experiments, we do not assume access to such information and apply the same problem-agnostic parameters uniformly across in- stances. Our empirical results strongly suggest that the algorithms are insensitive to these parameters for a wide- ranging degree of errors, and this might not be a limitation in practice.
We begin by establishing the survival probability of fixed minimum cut during a single randomized edge contraction. Lemma 2.1. Fix a weighted graph G, and let C" C (GG be minimum cut in G, with respect which 1j and p are defined. Now consider weighted graph G' (V, E.W) with k vertices obtained by sequence of edge contrac- tions starting from G such that no edge from C* has been contracted in any of these contractions. Let wp(e) = (1+ (B pe))u((e) for all edges e in E. Then the probability that none of the edges in C* is contracted in a single randomized edge contraction in G', where an edge e is chosen with probability wB(e)/ Ww ()), is at least qu, as long as k 2 2p + 2.
2. Boosted Karger's Algorithm
Proof. Let us start by observing that the probability that C* remains intact after a random edge contraction is 1- Wp (CB)(C///u(( Now we have
We discuss the Boosted Karger's algorithm, and we prove an improved lower bound for its probability of success. The algorithm has two parameters, scalar and a threshold. The algorithm boosts the edges in E \ C, meaning it multiplies the weights of the edges that fall outside the predicted set by a large scalar and then performs random edge contrac- tions similarly as in Karger's algorithm provided there is a sufficient number of vertices remaining. At this point, each remaining vertex (or properly, metavertex) corresponds to subset of the original vertex set. When fewer vertices re- main than the specified threshold, our algorithm reverts to the standard (i.e., not boosted) Karger's algorithm on the remaining metavertices.
wn(C') = Σ (1+ (B 1)(1 - ((1--)))uule po))
cEC²
= w(C*) (1 + (B- - (1)))-
Additionally, for the surviving edges E,, we have
wB Fb) = Σ + (B- 1)(1 pc))
EEE
Σ (B - (B - -1)p)w((e
eEE
> Bw(E) - (B 1)(pu((*) + (1 (1-7))a ())(("))
We refer to the steps on lines 3-6 of the algorithm above as
4

---

Faster Global Minimum Cut with Predictions
where the last derivation is an inequality for the sole reason that not all of the original false positive edges may have survived by this stage, that is, in earlier contractions used to arrive at G". Note that by now, since each (meta) vertex w corresponds to a cut in the original graph G, w(((v)) 2 w(O"), where ō(v) is the set of edges incident on v. Since every edge has two vertices, 2w(E) = Evev w(((v)). Therefore, we have
To conclude the claim, we invoke Lemma 2.2
Theorem 1.1 can now be obtained from Theorem 2.3 by choosing to be the smallest integer exceeding 3p and any B 2(logg n), because in the second phase Karger's algorithm ensures that the minimum cut has at least (21/tt²) probability of continued survival.
(E)
3. Boosting the Karger-Stein Algorithm
kw((") -(B (B - (2)(((((((C))))) -))((())
2 B
In this section, we present a variant of the FPZ algorithm due to Fox al. (2019) that utilizes predictions to improve over the running time of Karger-Stein.
Bk
(B - 1) (1 (1-)))) m))
w(C*)
2
The standard FPZ algorithm is the following. In the algo- rithm, % = 1- - 2/n is a lower bound on the probability that a fixed minimum cut C* remains intact after a single random edge contraction on vertices, assuming none of its edges have been contracted thus far.
We can now write
(C")")
wn(E) (E)
w(C') (B 1)n)
w(C*)
(1-1)))
Algorithm 2 FPZ(G,n)
qk.
Input: graph = (V, E, w) with n vertices. Parameters: branching factor d-
3: if n. = 2 then
Next, we state an elementary inequality that will be used to prove the main result of this section, Due to space con- straints, its proof is deferred to Appendix
4: return the set of edges in G between the two re-
maining metavertices.
5: end if
Lemma 2.2. For all t > 2p + 2, it holds
6: Pick an edge ē with probability x w((), that is, with probability w(e)/ EeEr w(e).
2(v+ 77))
II 4: 2 1=++1
t-- 2p- 2
Contract é in G produce G¹.
8: C1 FPZ(G', n -1).
9: With probability d'
We are now ready to prove the following theorem:
10: return GT.
Theorem 2.3. Let C* C E be a minimum cut in the weighted input graph G = (V, w), with respect to which n and are defined. Then, assuming t 2 2p+2 2, the prob- ability that none of the edges of C* are contracted in the first phase of Algorithm 1 is at least (1-2x 2p-2p-2 2(++ 2
11:
Otherwise
12:
C2 + FP).G.
13: return the cut from (C1, with the smaller
weight.
The boosted variant is follows.
Proof. Let E, be the event that none of the edges of C* are contracted in step i of the algorithm. At the start of step i, there are n 1 remaining vertices. Now, by Lemma 2.1 have
In this algorithm, In represents lower bound on the prob- ability that a fixed minimum cut C* remains intact after a single random boosted edge contraction on n vertices, assuming none of its edges have been contracted thus far. Given prediction Pe [0, 1] for each edge e, we apply our previous idea of reweighting the edges with parameter B to encourage the contraction of edges that lie outside the pre- dicted set. We also add switching point / to the algorithm, as we did before. Whenever fewer than t vertices remain in the graph, where t 2 3p + 2, the algorithm then invokes the standard FPZ algorithm. This time, we use
Pr Pr(Esl(Egtisc 2 Qn-i-l-
Let A be the event that none of the edges of C* are con- tracted in the first phase of the algorithm, that is, until there are at least & vertices left. Then, we have
Pr(A)= = Pr( Fi n... O Fn-+) (r(2 En) ... Pr(En- FF Eg. En-t-1)
> II 9:
1+ (B 1)m
In := 1 Bn/2- 1) 11))
1=H+1
5

---

Faster Global Minimum Cut with Predictions
Algorithm 3 BOOSTEDFFZZG,..) n.
approach can also be extended the weighted case, e-g.. using the Gumbel trick.
1: Input: graph G (V, w) with n vertices, predic-
tions {PeteEE.
A similar implementation can be performed for the Boosted FPZ algorithm. This will in turn enable the efficient run- time of our algorithm. The implementation of each random edge contraction must be carried out two cases, each uti- lizing a different data structure. The data structure used is based on the number of remaining vertices, n. as we detail next.
2: Parameters: scaling factor B, threshold t, branching factor 4n-
3: if 2 then
4: return the set of edges in G between the two re-
maining metavertices.
5: else if then
6: return FPZ n). In other words, run the standard
(non-boosted) FPZ algorithm.
If the number of remaining vertices is large enough, con- cretely, if > t, union-find data structure is used and the edges are sampled lazily without replacement, with proba- bilities proportional to their boosted weights. This is done until an edge found whose endpoints belong to different components. For sampling, categorical distribution over edges can be maintained online, for example, using red- black tree, while allowing sampling without replacement in (logm) time. To make recursive calls on the same graph, it is too inefficient to copy the graph and run recursive calls separately. Instead, the algorithm runs one call and then later returns to a possibly second recursive call, in a depth- first manner over the recursion tree. To accomplish this, we utilize a union-find data structure that supports dele- tions, which also takes O(log m) time in the worst case per operation (Alstrup et al. 2014).
7: end if
8: Let (e(()) == (1 + (B-)))1 ()(()))))w(()) for all e E F.
9: Pick an edge with probability w Eeeg WB(C)
and contract produce G².
10: C1 f- BOOSTEDFPZ((",,
1.p).
11: With probability Jn-
12:
return C.
13: Otherwise
14:
C2 - BOOSTEDDFZ(( p.p.
15: return the cut from [C1,C2] with the smaller
weight.
where 77 and p are defined with respect to C*, for n > f, and 9n. == 1 - 2/n for n < t. We refer to this modified version of the FPZ algorithm as the Boosted FPZ. First, we establish the following lower bound on the success proba- bility of the Boosted FPZ algorithm.
If n S t. we switch to an adjacency list data structure, which allows a random edge contraction in time propor- tional to the number of remaining vertices, as suggested in (Karger & Williamson 2021). When switching between these two regimes, we prune the list of remaining edges in (mm log m) time to ensure that there are at most t2 remain- ing edges. Once we are in the second phase, Algorithm is identical to the FPZ algorithm, the total run-time thereafter is ( log t).
Theorem 3.1. For any threshold t satisfying t 2 3p 2, the probability that Algorithm 3
returns minimum cut is
Ω
log loggn////))
Due to space constraints, the proof of the above theorem is deferred to Appendix(2 A
Next, we will analyze the running time of the algorithm.
Proof of Theorem 1.2 the expected running time of the algorithm on any call with k vertices and l edges left to process. Since we switch to the standard FPZ algorithm at / vertices, for all f", we have T(t, (¹) = O log t), which is the expected running time of the FPZ (Karger & Williamson) 2021). Note that, as mentioned above, we can assume
Let T(k; E) be an upper bound on
Let us take a moment to revisit a textbook implementation of Karger's algorithm that runs in near-linear time using Kruskal's algorithm. Recall, Kruskal's algorithm is typi- cally used for finding minimum spanning trees.
In the unweighted case, we start by creating uniformly random permutation of all edges and processing them se- quentially. Throughout the algorithm, we use a union-find data structure to check which nodes have been merged, This is used in the standard fast implementation of the tra- ditional Karger's algorithm. When processing an edge in this order, like in Kruskal's algorithm, any edge with both endpoints in the same connected component is discarded.
< <t in this case.
Then, we have the following recurrence for T(k, f), care- fully considering the number of edges processed in each iteration, via the union-find data structure, to carry out one edge contraction. The recursive expression can be ex- plained as follows: in any call, the algorithm processes f l' edges for some f", taking (e - L') O(log n) time. The algorithm then makes a recursive call on k - vertices and e' edges. Furthermore, with probability (1 - qx), the algorithm repeats itself on the input graph. For the analy- sis, we take the maximum over all possible values of e to
If an edge's endpoints are in different components, the union-find find data structure merges these nodes. The partition of vertices formed just before merging the last two con- nected components, is returned as the minimum cut. This
6

---

Faster Global Minimum Cut with Predictions
consider the worst case for the algorithm.
Here e is a variation of p defined as:
T(k. f) - max - 1. + (1-9g)T(ke)
(GG = (1- W. - (.)
(CG(C*(G)
+ (e- - -0000) n)}-
where (=( is the characteristic weight vector of the minimum eut (G),,, that is, it is vector in [0, 1]()), with its entry corresponding to e equal to wa(e) if e E (G), and zero otherwise. Note that p(G.p) 2 p(G,p) p) for all p. and therefore U(G,p) p) is a valid up- per bound on R(G.p). It is instructive to compare p and p for unweighted graphs. For unweighted graphs, p(G,p) = LEEBIGNC- Pe/ Pe/wa(C*(G)) and (G (X)orra)) Pe/ Pa/wa(C" (G)). Thus, the principal differ- ence between the two is that p(G, p) additionally accounts for erroneous predictions that correspond missing edges.
This inequality can be simplified to:
1 max (T(H: 1, + (e- Ollogn)) 4h
T(k,))
ise'
Unfolding the right-hand side, we get:
4 Ollogn) n)
T(n, m) S max
Σ ==++
4 S m
Iisssn Zi
i=++1
t logt
+0
Il++1si5n 91)
O(m log n + e log 1)
Unfortunately, U p) is also not convex in p (see Proposi- tion A.1 Our key observation is that upon replacing 1 1 p,, which appears naturally in the definition of p. with free variable, the resultant analogue of ()G.p) becomes con- vex in p (see Proposition A.3). Since 1 p is an instance- independent scalar, its best value can be estimated through grid search, in addition to running copies of online gradi- ent descent on p corresponding to all possible values of the free variable in the grid. In Appendix[A.] we prove:
Metsssaa Oj
Using Lemma 2.2 to lower bound the product of (g by setting B 92 log n), for any 2 3p 2, get
mm, = O ( m logogn n + logt (t/n)ay
vm) concludes the claim. Setting / = max max[[3p+ [3p+
Theorem 4.1. For any E, an algorithm with the following properties. Given poly(n, 1/ 1/Cmin, log(1 (eo)))/))/ ii.d samples from any dis- tribution D, satisfying that Cmin is a lower bound on the size of the minimum cut of any graph in D's support, the algorithm runs in poly(n, 1/E, 1..11/e 1/Cmins (og() time and oulputs a prediction E [0, (((²) such that, with probabil- ity at least 1 1- 8. we have
O, there exists
4. Learning Near-Optimal Predictions
In this section, we describe how near-optimal predictions can be learned from past data. Formally, we assume that there is an unknown fixed distribution DD on weighted graphs that share the same set V of vertices, from which a number of samples are drawn independently. Given these samples, our goal is learn near-optimal predictions p" E [0, ()x) that minimize the expected runtime of the Boosted Karger's 's algorithm with respect to D.
EGGD (U(G,p) - arg min EG-D (U(G. S.. (3)
Let (G) denote a minimum cut in G. For a prediction p. let ()(p)) and p(G.p) p) denote the false negative and false positive with respect to C²(G) and p. respectively. Note assume, without loss of generality, that 0 I wa(e) < 1 for all E E(G). Otherwise, we can scale all edge weights so that they are within the interval [0, 1], and this would not change C","), and Since the edge sets of the sampled graphs may differ, we will assume the vector of predictions p is defined over (*)
The time and sample complexity above scale with 1/ 1/Cmin- Such dependencies occur regularly while learning real- valued functions without uniformly bounded derivatives (see, e.g., Chapter 4 in (Hazan et al. 2016)). For un- weighted graphs, one may always assume that Cmin 2 1.
that
5. Experiments
We aim to demonstrate that the theoretical advantages pre- sented in the previous sections also translate to improved empirical performance. We perform three sets of exper- iments The first involves synthetic settings where we can explicitly control the fidelity of predictions to study the
We have established that the expected running time of the Boosted Karger's algorithm is at most R(G,p) == S
2n( ((GG)) pG31))(G.P)) A natural strategy for learn- ing near-optimal predictions is to compute predictions that minimize this running time upper bound averaged over col- lected samples. However, R(G.p) p) is nonconvex in p. In- stead, we aim to optimize (G.p) = n nn((..p) p(G.
'The Python implementations of the experiments are avail- able at httpss//gtthcccooccciaiaipaar/ap mwwpa//ppaass/aaaaammmmmmmnmmmaa with-predictions
7

---

Faster Global Minimum Cut with Predictions
performance of the algorithm quantitatively. The second is setting where Karger's algorithm is used repeatedly find minimum cuts on a family of instances that organi- cally arise from trying to solve traveling salesperson (TSP) instances. We conclude with experimental comparisons on real data.
5.2. Minimum Cut Instances from the TSP LP
In the second set of experiments, we explore instances in which predictions appear naturally. Cutting plane algo- rithms for the traveling salesperson problem (TSP) proceed by repeatedly identifying subtour elimination constraints in the subtour linear program relaxation for TSP, the search for which can be recast as finding global minimum cuts (see, e.g., (Chekuri et al., 1997)). We use this practical use case of Karger's is algorithm to evaluate the performance of the Boosted Karger's 's algorithm.
5.1. Controlled Experiments on Synthetic Graphs
In the following set of experiments, we explicitly control the prediction quality and measure the performance of the proposed algorithm against Karger's s algorithm on a family of synthetically generated graphs. We are especially inter- ested in:
The subtour elimination approach to TSP starts by mini- mizing Eeeg Wg subject to EEEN(e) Ze = 2 for all nodes v E V and 0 < Te < for all e E F,, to obtain an initial solution x². This linear program is known as the subtour relaxation. Then, a new graph Go is built with the same set of vertices and edges as the original, but with the difference that the weight of edge e in Go is n0 Note that if the entire vector x" is integral, then I. represents a Hamil- tonian cycle. and the size of the minimum cut in Go is 2.
1. How the Boosted Karger's algorithm compares to the original Karger's algorithm, especially instances where the latter requires many repetitions to succeed.
2. How the asymmetric error measures 1j and p affect the number of trials that the Boosted Karger's algorithm needs to find the minimum cut.
The issue is that the edges maybe fractional and the goal is to find a constraint to add to the program based on x". Upon finding a minimum cut in Go. if its size is smaller than 2, the following subtour elimination constraints are added to the above LP and the LP is solved again.
A bipartite graph G with vertices is built as follows. Each partite set has n/2 vertices, and the edges consist of ran- dom perfect matchings. First, k random perfect match- ings are added to the graph, and then an arbitrary vertex is picked and of its incident edges are randomly chosen and removed from the graph. These instances are designed to be difficult for Karger-like algorithms because they con- tain many near- minimum-cut-ssiie cuts, each of which has a healthy probability of survival via random edge contrac- tions.
Σ Ie S |S - 1, and Σ e=/u,0)
I S 1121 - 1,,
c= (u.e)
M.0ES
a,
where (S),Sc is the vertex partition for the minimum cut found in Go. This process is repeated until the minimum cut in the current graph is of weight 2. Thus, global min- imum cuts used generate constraints for the subtour relaxation.
To generate predictions, we first compute the true minimum cut C on G. Now for any given 7) and p. we pick two random subsets C22 S C* and Cp S E \ C", such that w(C,)) (C)) and w(C,) = =pw(C*) Our predicted VC,''CCUC C..
To begin, we first construct a TSP instance. A random graph G = (V, with n vertices is built as follows. The vertices are partitioned into two subsets S and T of equal size, and the edge set consists of a number of ran- dom cycles. First, k random Hamiltonian cycles are added to G with the guarantee that each cycle crosses the parti- tion (S, in exactly two edges. Then, k random cycles of length n//2 are added to each of S and T. Finally, ek smaller random eycles, each having a random length be- tween and n/2 - 1, are added to G, making sure that these cycles do not cross the partition.
edge set is Co = C' =C'
We build G with n = 600, k = 100, f = 10. We note the number of trials that Karger's algorithm needs G to find the minimum cut. This is our baseline. Next, we fix a value of E {0, 10, 100), and for each value of E {0, 0.05, 0.1, 0.1,..., 1}, we measure the number of trials Boosted Karger's 's needs to find the minimum cut with input (G, Cr,p)) with (B,t) = (n. 2). In Figure this process is repeated 30 times.
We obtain sequence of graphs Go. GI...., Ge, for which we want to find the minimum cut. We predict that none of the edges with integer weights appear in the minimum cut. Therefore, for each graph G;, the predicted minimum cut C is the set of all edges with fractional weights. These are natural and easily computable predictions.
We can see that the Boosted Karger's algorithm outper- forms Karger's algorithm by two orders of magnitude when 7) S 0.5 and E {0, 10). Furthermore, even for p = 100, indicating especially poor prediction quality, since the pre- dicted set of edges is about a hundred times as numerous as the size of the minimum cut, Boosted Karger's 's algorithm is better by one order of magnitude when 7) E 0.6).
We build G with n 500, k = 50, e = 0.5, and construct
8

---

Faster Global Minimum Cut with Predictions
390
493
409
392
L0CE-
Sanded
0.2
3.4
0.2
0.6
00
Figure I. A controlled experimental comparison of the number of repetitions Boosted Karger's algorithm needs to find the mincut vs. the standard Karger's algorithm for different quality of predictions, as parameterized and p.
Go...., Gv. Then, we do the following steps for each E [e]. On each minimum cut instance we obtain, we measure the number of iterations needed to produce the minimum cut for Karger's and for Boosted Karger on (G;, C:). We (B,t) (log n, 2). These steps are repeated 10 times.
close to the minimum degree of the graph. This process is repeated 100 times in Figure2B. We observe that for all three datasets the Boosted Karger's algorithm requires dis- cernibly fewer number of trials to find the minimum cut.
1820-193
In Figure A evaluate both algorithms and observe that the Boosted Karger's algorithm consistently outperforms Karger's algorithm. In particular, it achieves an order- of-magnitude improvement on the harder instances where Karger's 's algorithm requires many repetitions to find the minimum cut.
200-
500
200
115
1-212
150
Figure 3. In the figure above, is demonstrated the number of rep- etitions needed to recover the minimum cut on three real graph datasets.
125
100
75
50
6. Conclusion
25
baceted
We explored how predictions about the minimum cut can impactful boosting the performance Karger's and the Karger-Stein algorithms. Furthermore, we empirically demonstrated that the Boosted Karger's algorithm signifi- cantly outperforms Karger's algorithm even when predic- tions have relatively high eгror. The paper shows that Karger's 's algorithm can naturally be improved with predic- tions, and a natural direction for future research to ex- plore how predictions may be applied to speed up other combinatorial optimization problems. Furthermore, our al- gorithm needs prior upper bounds on the magnitude of er- ror (as specified by 1) and p), and developing algorithms that are oblivious to such error measures remains an open problem. It would also be interesting to consider other pre- diction models for our problem, for example, representing the predictions as a partition of the vertex set rather than as subset of edges.
Figure 2. In this figure, compare the number of minimum cuts arising from subtour TSP that Karger's and Boosted Karger's 's algorithms solved within given number of repetitions.
5.3. Real Datasets
Finally, we compare the performance the Boosted Karger's algorithm and the standard variant on three real datasets Rossi & Ahmed (2015). For each dataset, the predictions are obtained by first randomly sampling half of the edges and then performing k parallel runs of Karger's 's algorithm on the sampled edges. The predicted edge set is formed by the union of the edges of the & cuts found by Karger's algorithm. As a heuristic, we pick i

---

Faster Global Minimum Cut with Predictions
Impact Statement
pdf
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences our work, none of which feel must be specifically highlighted here.
Fox, K., Panigrahi, D., and Zhang, Minimum eut and minimum k-cut in hypergraphs via branching contrac- tions. In Proceedings of the Thirtieth Annual ACM- SIAM Symposium Discrete Algorithms, pp. 881-896. SIAM, 2019.
References
Alstrup, S., Thorup, M., Gørtz, I. L., Rauhe, T., and Zwick, U. Union-find with constant time deletions. ACM Trans. Algorithms, 11(1):6:1-6:88 2014. doi:
Gabow, H. A matroid approach to finding edge connectiv- ity and packing arborescences. Journal of Computer and System Sciences, 2(50):259-273) 1995.
10.1145/2636922. URL https://doi.ooe 1145/2636922
Gomory, R. E. and Hu, T. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathe- matics, 9(4):551-570, 1961.
Botafogo, A. Cluster analysis for hypertext systems. In Proceedings of the 16th annual international ACM SI- GIR conference Research and development in infor- mation retrieval, pp. 1 116-125, 1993.
Hagberg, A., Swart, J., and Schult, D. A. Exploring network structure, dynamics, and function using net- workx. Technical report, Los Alamos National Labo- ratory (LANL). Los Alamos, NM (United States), 2008.
Chatterjee, S., Gilbert, J. R., Schreiber, R., and Sheffler, T. J. Arra distribution in data-parallel programs. In Languages and Compilers for Parallel Computing: 7th International Workshop Ithaca, NY, USA, August 8-10, 1994 Proceedings 7, pp. 76-91. Springer, 1995.
Hao, J. and Orlin, J. B. A faster algorithm for finding the minimum cut in directed graph. Journal of Algorithms, (733):24-446, 1994.
Hazan, E. al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157- 325, 2016.
Chekuri, C.,, Goldberg, A. V., Karger, D. R., Levine, M. S., and Stein, C. Experimental study of minimum cut algo- rithms. In SODA, volume 97, pp. 324 333, 1997.
Henzinger, M., Rao, S., and Wang, D. Local flow parti- tioning for faster edge connectivity. SIAM Journal on Computing, 49(1): 2020.
Chen, J., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp. 3583-3602. PMLR, 2022.
Henzinger, M., Li, J., Rao, S., and Wang, D. Deterministic near-linear time minimum cut in weighted graphs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 3089-3139. SIAM, 2024.
Colbourn, C. The combinatorics of network reliability. Oxford University Press, Inc., 1987.
Davies, S., Moseley, B., Vassilvitskii, S., and Wang, Y. Predictive flows for faster fuld-fulkerson. In Interna- tional Conference on Machine Learning, pp. 7231-7248. PMLR, 2023.
Im, S., Kumar, R., Petety, A., and Purohit, M. Par- simonious
caching. In Interna- tional Conference on Machine Learning, pp. 9588 9601. PMLR, 2022.
Dinitz, M., Im. S., Lavastida, T., Moseley, B., and Vas- silvitskii, S. Faster matchings via learned duals. Ad- vances in neural information processing systems, 34: 10393-10406, 2021.
Im, S., Kumar, R., Qaem, M. M., and Purohit, M. Non- clairvoyant scheduling with predictions. ACM Transac- tions Parallel Computing, 10(4):1-26, 2023.
Dinitz, M., Im, S., Lavastida, T., Moseley, B., Niaparast, A., and Vassilvitskii, S. Binary search with distributional predictions. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. (eds.). Advances in Neural Information Processing Systems, volume 37, pp. 90456-90472. Curran Associates, Inc., 2024. URL lattps::/proceeddinng new.ips. cc cc/ Sc/paper filess/papper/2224//LL
Karger, D. R. Global min-cuts mnc and other ramifica- tions of simple min-cut algorithm. In Soda, volume 93, pp. 21-30. Citeseer, 1993.
Karger, D. R. Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46-76 2000.
Karger, D. R. and Stein, C. A new approach to the mini- mum cut problem. Journal of the ACM (JACM), 43(4): 601-640, 1996.
10

---

Faster Global Minimum Cut with Predictions
Karger, D. R. and Williamson, D. Recursive random contraction revisited. In Symposium Simplicity in Al- gorithms (SOSA), pp. 68-73. SIAM, 2021.
Rossi, R. A. and Ahmed, N. K. The network data
repository with interactive graph analytics and visual- ization. In Proceedings of the Twenty-Ninth AAAI Con- ference on Artificial Intelligence, 2015. URL http:
Kawarabayashi, K.-i. and Thorup, M. Deterministic edge connectivity in near-linear time. Journal of the ACM (JACM), 66(1):1-50 2018.
//networkraposiieee
com
Saranurak, T. A simple deterministie algorithm for edge connectivity. In Symposium Simplicity in Algorithms (SOSA), pp. 80-85. SIAM, 2021.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pp. 489-504, 2018.
Siek, J. G., Lee, L.-Q., and Lumsdaine, A. The Boost Graph Library: User Guide and Reference Manual, The, Pearson Education, 2001.
Lattanzi, S., Lavastida, T., Moseley, B., and Vassilvitskii, S. Online scheduling via learned weights. In Proceed- ings of the Fourleenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1859-1877. SIAM, 2020.
Stoer, M. and Wagner, F. simple min-cut algorithm. Journal of the ACM (JACM), 44(4):585-591, 1997.
Lattanzi, S., Moseley, B., Vassilvitskii, S., Wang, Y., and Zhou, R. Robust online correlation clustering. Ad- vances in Neural Information Processing Systems, 34: 4688-4696 2021.
Li, J. Deterministic mincut in almost-linear time. In Pro- ceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 384-395, 2021.
Li, and Panigrahi, D. Deterministic min-cut in poly- logarithmic max-flows. In 2020 IEEE 61st Annual Sym- posium on Foundations of Computer Science (FOCS), pp. 85-92. IEEE, 2020.
Lindermayr, A. and Megow, N. Permutation predictions for non-clairvoyant scheduling. In Proceedings of the 34th ACM Symposium Parallelism in Algorithms and Architectures, pp. 357-368, 2022.
Lykouris, and Vassilvitski,, Competitive eaching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
McCauley, S., Moseley, B., Niaparast, A., and Singh, S. In- cremental topological ordering and cycle detection with predictions. In Proceedings of the 41st International Conference on Machine Learning, pp. 35240-35254.
PMLR, 2024a.
McCauley, S., Moseley, B., Niaparast, A., and Singh, S. Online list labeling with predictions. Advances in Neural Information Processing Systems, 36, 2024b.
McCauley, S., Moseley, B., Niaparast, A., Niaparast, H., and Singh, S. Incremental approximate single-source shortest paths with predictions, 2025. URL https: //arxiv.orge abss//aa//aa 250. 08125
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Communications of the ACM, 65(7):33-35, 2022.

---

Faster Global Minimum Cut with Predictions
A. Missing Proofs
Proof of Lemma
2.2
We first apply the inequality
2 el-=, which holds for all 1, get
1 (B - 1)n
1+ (B 1)m
II
Σ
B pp 7/13
exp
B(i/2 - 1) 11 (B 3 1)p
i=t+1
2
Bi/2 (B-1)p )
1 (B-
= cxp
Note that for non-decreasing function f. we have f (x)ddo S EiEL f(i). Therefore, we can write
2
1B - 1)7
m- 1+ 1B -18-111 -)) (-)ma²
exp
Σ
Bi/2- (B -11--11p 2 exp
J-2 Bx/2 - (B -1)p dr
The condition t 2p ensures that f non-decreasing in the desired interval. From here, we just need to carry out the calculations and simplify the expressions:
exp (-/ra²
2+2 2(B 1)m dx
m dr
exp
- -2+ 1)m)
Bx BBB - 1)p
J-- Br - 2(B 1)p
22+ 1)m)
exp
In (Bx - 2(B 1)p) 1
B
2+2(1-199
B(t - 2) - 2(B 1)p
B(n - 2) 2(B 1)p
2(0
B(I 2-1-2-20 2p) + 2p
Bn - -2B 2( - 1)p
B(t 2 2p) 2(1+ 42)
Bn
Proof of Theorem 3.7 Let C* be the minimum in G that is used to define and p, and let P(i) denote lower bound on the probability that the algorithm returns C", given that all edges of C" have survived contractions up to the point where i vertices are left. Once there are fewer than remaining vertices, Algorithm 3 proceeds identically to the standard FPZ algorithm. Thus, utilizing the result from Karger & Williamson (2021). we have that P(t) = 1/(2HH, 2).
For the first phase, that is, when there are at least t remaining vertices, we will be able to reuse the following recurrence for P(n) from Karger & Williamson (002)) although the value of the branching factor (compare d' and qu.) now different.
P(n) = P(n - 1) + (1 (1- g1) (1- ((m))( - 9n P(n - ())).
a lower bound on the probability that C* survives yet another randomized edge con- traction. The recurrence is derived by noting that with probability qa. line 12 is executed, after which the probability of returning a minimum cut is least In P(n 1). With the remaining probability
As observed in Lemma 2.1
qn both paths computing the minimum cut through recursive calls on instances of size n and n must fail for the algorithm to miss the minimum cut.
This recurrence can be simplified to:
1
+ Jn.
P(n)
P(n P(n-1)
12

---

Faster Global Minimum Cut with Predictions
Unrolling the recurrence, get
1 P(n)
+
(1 (1-%)
P(I)
i=1+1
1+ (B - 1)m
211, -2
Bi/2 1 (B- (p+ (1-1))
i=1+1
1+ 1)n
2111 2+
Bi/2 - (B- (p+ (1 11) di
21 (B 1)m)
BBn/2 (B 1)(p + (1 (1-1)) Bt/2 -B (B- 1)(p (1 -())
=21,, 24
In
B
=0 -10g ( + 17 1og 7)
where we use the fact that /"= (x))dx
s Ei f(i) holds for any non-decreasing function f. and in particular for
f(x) = 1/2. This concludes the proof.
A.1. Learning Near-Optimal Predictions
We begin by proving the following two propositions, which motivate our learning algorithm.
Proposition A.1. The function (G) is not convex in
Proof. The hessian of U(G w.r. p is as follows:
2n2n(G.p)
(UU(G
(1 (1-w,(G) 2nn p(GG w. (G))
we wa(C" (G)))3
(1 w. (G) 22n p(G.p) w. (G))
-2(In p(G.p) - w. (G)) Inn G(G, p) w. (G))
Being a difference of two rank-one matrices, the hessian is not positive semi-definite. Concretely, consider the following simple example demonstrating that V²U(G, p) is not positive semi-definite, which means that U(G, p) not convex in
p. Consider the following graph 3 vertices with the edge weights written next to them. Let p( (1,2 1/ In 3, and (((233)) 3((1,3)) = 0.
3
0.7
0.6
2
Then, we have
2n pni..p
-0.16
-0.4 -0.4
-0.4
VUU(,p))
1
1
(G))2
-0.4
1
1
which is not positive semi-definite
Nevertheless, we will succeed in minimizing ((G.p) over p. To build towards this, consider the following function formed by replacing 1Tp in (G, p) by a free variable
13

---

Faster Global Minimum Cut with Predictions
Definition A.2. For b 2 0, define
(o ( (G(C+(())
(wa (w) and K₂ = {p E (0, (0.1(()) 1'p s b).
() == :
We have the following proposition.
Proposition A.3. For all 2 0, (G, is convex in p over Kb-
Proof. The hessian of (G, w.r.t is as follows:
(CU'(G,))= n p.)
4In2n n 0 (w> (G.P))
(w-(w,
(~w((C-())) + 88lun ("wc(C+(()) +
(G))3
x (G) (G)"
The coefficient w. (G) (G) in the expression above is non-negative whenever E Kg. Therefore, the hessian is positive semi-definite on the interior Kg. which means (G. convex over Kg.
Now, we describe our proposed algorithm to compute a prediction given a polynomial number of i.idd samples drawn from D, and then analyze it to prove Theorem 4.1
The Learning Algorithm. To begin, we draw T ii.d samples GI...., Gr from D. We discretize the range of possible values for (which represents T p). i.e., [o, (?)] into equally sized intervals, and optimize over each them separately. Let be set of discrete values considered for b; we will specify the resolution the grid later.
For each b E we perform online gradient descent on the sequence (G..)))) of convex functions over the convex body K2 to obtain the set of vectors [p!]T C Kb, as stated below:
II [pt ne T.. pl+1
where Uk [x] arg min || 2l12. Let Po = + Et pi for all b e B.
Next, draw T" new i.idd samples Gí ,.,..., GT from D and compute + Et" U² (G'',, pb) for each b B. Let V arg min 1. Σ U' Po). The algorithm outputs py. The values of nt. T, T', and the cardinality of B will be determined in the analysis.
We start the analysis with the following guarantee:
Theorem A.4 (Theorem 3.1 in Hazan et al. (2016). For a fixed b B, let Q be upper bound on (G.,)ll all (t, p) E [T] x Kb, and let D be an upper bound on ||p 4l12 for all p,q Kb. The iterates produced by Online Gradient Descent with step sizes т)- = D/ Qvtl guarantee that:
T
Σ 1=1
(GGP))
min Σ PEKa t=1
3 (G,,p) QDVT.
2
To use the above theorem, note that
2n (G(.p)
b (w. Inn wc(C*(G))
( (b-(w.(G).)) + Ww((C(()) w. (.).).
2
(U'(G. = wG (G))
Let Cmin == inf infpe)))) we (G)). Then, the guarantee in Theorem A.4 is obtained by setting Q = 2n. In n/O Cn D = n; these valid upper bounds on size of the gradients and the diameter can be readily verified.
For each b E B, let Regret, = Σt= Uh p/)
minpe K, Σt= U'(Gr, p). Now, we utilize the following theorem:
14

---

Faster Global Minimum Cut with Predictions
Theorem A.5 (Theorem 9.5 in Hazan al. 2016)). For a fixed and any 0, given T i.i.d samples drawn from D, with probability at least 1 8, have
Regret
8 llg (3)
(G.)
+|
T
T
where P arg min BGND (G.p)
Let p" = arg pen Bc- (U, p)], where K = [0, [0,1](2), and let 6* = p=p'. Let E B be the smallest element in B
that is larger than or equal to b", and suppose b-b- S A. Let L(G, p) be the Lipschitz constant 2n((.r) (b-(w. (G) 2 function of b. Then, have
(C'((""G))
EGND LU (G, & BGND(U (G,p")++ LA = (CoDDU((,,)) LA,,
where L is an upper bound on L(G,p) for all G in D's support and E K. Note that A and L can be chosen such that I 2²/[B] and L < 2n /C
Let M be an upper bound on (G. U (G, g)) for all E B, p.q E K₁ and G in D's support. We can pick M such
that M S nC Then, by the Chernoff- Chernof-HHoeffdnn Hoeffding inequality and union bound, if T" 2())² log B ))) then
with probability at least 6, for all b B, we have
1 T"
Σ EAND (U' [b)] - T
(G,
Se.
Therefore, using the fact that is chosen to minimize the empirical average, we have
1 T'
EGND J0 (G. (G, (G)
<
Σ U
(v)
+Es
1
U +e BOND [u}(G.Pb) + +2.
T
T
Finally, by Theorem A.5
we have
EGLD [ < EOND (G.)))))) +
Regret T
8 log (3)
T
Putting everything together, we can write
EAND 1 (G,w))
S EOND (G,P))) + 2
Regret, T
8 log (2)
< EOND (²( (p)
+
+ 2
T
< EOND [T}(G.P))
Regret T
8 log (2)
+
+ 2
T
8log (2) Regret
< EOLD [[G.p')) LA +
+
+ 2s.
T
Therefore, we need [B] @(n9/eC2 / min) and T O max (
(QD)²
[QD]
2
2z log 1
b
to obtain the promised guarantee.
15


Reviews:
[{"review_id": "DgKn12kw4J", "reviewer": "Reviewer_Na2d", "summary": "The paper studies global minimum cut with predictions. The problem is given a weighted graph $G$, find a partition of the vertices $S, V \\setminus S$ that minimizes the total weight of edges crossing the cut. Without predictions, there are two main baselines: first a naive version of Karger's minimum cut algorithm which runs in $\\tilde{O}(n^2)$ time and succeeds with probability $\\approx 1/n^2$. The second is a smarter version of Karger's algorithm that runs in overall $\\tilde{O}(n^2)$. \n\nThe authors present improvements on both of these algorithms using an oracle which gives a predicted set of edges constituting the minimum cut (the authors generalize this to the case where the predictions give a fraction for every edge being in the minimum cut). The two main notions used to measure the error of the predictions are false positives and false negatives (weighted fraction of edges which are incorrectly stated to be in min cut compared to opt vs weighted fraction of edges which are erroneously left out compared to opt). Interestingly the two types of errors have different influences on the final error.\n\nThe most interesting regime seems to be for sparse graphs. Assuming that false positives are $o(n)$ fraction of the actual min cut, the submission is able to get a near linear time bound. The main, and quite natural, idea is to boost the probability of picking edges that are not predicted to be in the min cut in the contraction steps of Karger's algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We would like to highlight the following points:\n+ **Theorem 1.2:** We agree with the reviewer’s observation regarding Theorem 1.2, but this is already taken care of in the theorem statement. Note that the bound in Theorem 1.2 is an ($\\eta$-weighted) geometric mean of $m$ and $n^2$, and hence, is always $\\Omega(m)$.\n+ **Insensitivity to oracle parameters:** Regarding empirical evidence of robustness to knowledge of false negatives and false positives, we refer the reviewer to the first set of experiments, as shown in Section 5.1 and Figure 1. In these, regardless of the value of $\\eta, \\rho$, without any tuning, we set $(B, t) = (n,2)$ in the algorithm. Yet the algorithm demonstrates a marked improvement over Karger’s empirically for a wide variety of settings.\n+ **Vertex-partitioning predictions:** We appreciate the suggestion to investigate vertex-partitioning predictions. In our setting, predictions on edges provide richer information about local pairwise interactions, and our analysis leverages these interactions for robust guarantees. As stated, we do not place any restriction on such predictions, i.e., they may not come from a cut. Note that vertex-based binary predictions can always be translated to edge-based predictions, while the reverse translation is not always possible; thus our prediction model is more generally applicable. The appropriate treatment of probabilistic predictions (as almost all ML models avail us) is also more subtle for vertex-partitioning predictions. All said, deriving faster algorithms based on vertex-based predictions with runtime parametrized by the right characterization of error in such models remains an excellent direction for future research.", "claims_and_evidence": "Yes, the theorem statements seem to have correct proofs.", "methods_and_evaluation_criteria": "I have some slight issues with the experiments, see below.", "theoretical_claims": "I did not check too closely but the main ideas made sense to me. There is one minor question: Should theorem 1.2 have a $+ O(m)$ factor in the running time since we need to read the graph?", "experimental_designs_or_analyses": "The experiments seem sound but there are some drawbacks:\n\n- One needs to know the values of false positive and false negative rates to initialize the algorithm. While the authors claim that the algorithm is insensitive to such parameters, there was not an extensive empirical evidence for this. It would be better to have a version of the theoretical algo , maybe with slightly worse guarantees, but that is robust to miss-specification of these parameters. \n- The augmented FPZ algorithm, which is the main technical contribution, is actually not implemented. Thus, the traditional \"optimized\" version of Karger may actually be faster in practice.\n- Details on n and m are omitted for the real datasets. Overall, both synthetic and real world graphs seem to be really tiny. \n- Figure 2A is missing error bars", "relation_to_broader_scientific_literature": "Perhaps the datasets in [1] below could be a good test bed since they test learning augmented graph algorithms on actual large graph datasets (which are varying across time so getting predictions is quite natural).\n\n[1] Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR 2022", "essential_references_not_discussed": "None, the submission is pretty self contained.", "other_strengths_and_weaknesses": "- Pro: boosting the weight of an edge based on its prediction seems a natural idea and it's great that they could execute this plan. I think this could be a useful meta idea for future learning augmented works and i find this conceptually very interesting.\n- Con: Vertex predictions seem more natural in this case? For example, edge predictions could lead to inconsistencies (that maybe one can trivially fix which doesn't seem that natural?) For example, if the prediction says edge (a,b) is in the min cut and (c, d) is in the min cut, then it should imply something about the edges between these vertices as well. However this information is not used or doesnt seem to matter which I find a bit strange.\n\nOverall, I am leaning towards acceptance.", "other_comments_or_suggestions": "None.", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wRR9v8bYNJ", "reviewer": "Reviewer_CqeQ", "summary": "This paper presents an adaptation of two randomized algorithms for\nmincut to take into account predictions about whether specific edges\nappear in a minimum cut. For the simpler of the algorithms, the change\nconsists in simply making a randomized choice of edge by weighing the\nedges by the prediction. The paper proves the modified algorithm has\nimproved probability of finding a minimum cut, under generous\nassumptions for the error in the prediction. It also proves that it is\npossible to learn such predictions with small error and small sample\nsize. An experimental evaluation shows more specific data on the\nperformance of these algorithms in practice.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review, and for appreciating our transparent writing style.", "claims_and_evidence": "The claims are well supported, both theoretical and practical", "methods_and_evaluation_criteria": "I had doubts about the setting of graphs with the exact same set of\nvertices, but the scenario of using this in the context of solving a\nTSP made sense.", "theoretical_claims": "I have not checked the proofs in detail.", "experimental_designs_or_analyses": "I found no issues.", "relation_to_broader_scientific_literature": "The paper follows a large body of work (correctly cited) on using\npredictions to improve existing algorithms.", "essential_references_not_discussed": "None that I know", "other_strengths_and_weaknesses": "I liked the writing: factual, honest with respect to drawbacks, to the point.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wMlvT35vnZ", "reviewer": "Reviewer_VTdE", "summary": "Algorithms for boosting minimum cut algorithms with predictions are studied. The authors propose two methods: the boosted Karger’s algorithm and the boosted Karger-Stein method. These methods rely on predictions from a machine learning model to guarantee multiplicative improvements in runtime (Theorems 1.1 and 1.2).\n\nAdditionally, the authors describe how, given samples from a fixed random graph model, to efficiently find predictions that minimize an upper bound on the expected runtime of the boosted Karger’s algorithm. \n\nEmpirical results on synthetic and real datasets demonstrate the efficacy of the boosted mincut algorithms over their non boosted counterparts when predictions are provided. A practical application to accelerating LP TSP relaxations via subtour elimination is also demonstrated as well as three real network datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review. We see our work as a first step in speeding up a fundamental combinatorial optimization problem, and we certainly agree that extensively assessing and demonstrating the empirical performance improvements of prediction-augmented algorithms for such problems is both warranted and a valuable avenue for future work.", "claims_and_evidence": "The authors study two classic minimum cut algorithms augmented with predictions. Several theorems characterizing the runtime of these algorithms in terms of the quality of predictions are provided. Additionally, an algorithm to learn optimal predictions  (with respect to the runtime of the proposed prediction-augmented cut algorithms) from data is designed and its runtime is characterized. These bounds are justified both via proof and empirical evidence on a variety of synthetic and real datasets.", "methods_and_evaluation_criteria": "The proposed evaluation criteria (synthetic random bipartite graphs, TSP problems, and real graph benchmarks) are reasonable.", "theoretical_claims": "I have checked results and proofs in the main text and results in the appendix related to the learning algorithm.", "experimental_designs_or_analyses": "Empirical evidence includes experiments on synthetic and real datasets, demonstrating the efficacy of boosted algorithms over their non boosted algorithms over a range of controlled predictions qualities", "relation_to_broader_scientific_literature": "Research into how predictions may inform classic algorithms has important implications in many fields. This paper serves as a good benchmark for how a thorough analysis might be conducted.", "essential_references_not_discussed": "I am not aware of missing relevant citations.", "other_strengths_and_weaknesses": "Strengths: The authors study variations of two min-cut algorithms with prediction advice and provide a novel analysis and suite of results to characterize how the quality of the predictions may be used to augment minimum cut algorithms. The topic is an interesting and important, and this paper serves as a nice contribution. The authors demonstrate how one may learn predictions to minimize the expected runtime of the two algorithms. Empirical evidence on synthetic and real benchmarks is provided to demonstrate how predictions may assist. The paper well-written. The analysis is comprehensive and technically correct. Code is provided, which is appreciated.\n\nWeaknesses: The experiments are somewhat limited in scope. I would expect some empirical investigation of how the learning algorithm performs and associated bounds on the expected runtime.", "other_comments_or_suggestions": "\"predictioas\" typo in conclusion", "questions_for_authors": "I have no pressing questions at this time. I would be happy to see this paper in icml.\n\nAlthough I would be happy to see empirical performance on a wider range of random graphs (e.g. other clustered random graphs), and an empirical demonstration of the k-cut Kargers algorithm.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ux7nZTCV5w", "reviewer": "Reviewer_LZnM", "summary": "This paper investigates how predictions can be used to improve the running time of classic algorithms for the global minimum cut problem. Given a weighted graph $G$, the classic algorithm of Karger repeatedly selects edges randomly, proportionally to their weights, and contracts them until two vertices remain, which define the final cut. \n\nIn this paper, the authors propose a prediction-augmented framework that modifies Karger’s algorithm by boosting the weights—and consequently the contraction probabilities—of edges that are predicted not to be part of the minimum cut. The algorithm operates by defining a threshold parameter $t$: while the graph has at least \n$t$ vertices, edge contractions are performed based on the boosted weights, after which the algorithm switches back to the classic Karger algorithm for the remaining steps. A similar boosting strategy is applied to the FPZ algorithm of Fox et al. (SODA 2019) to improve the running time of the Karger-Stein algorithm through prediction-guided edge contraction. \n\nThe paper provides theoretical guarantees showing that, with good predictions, the learning-augmented algorithms recover the minimum cut with high probability, resulting in improved runtime. The analysis characterizes performance in terms of the total weight of false negative edges (respectively, false positive edges) over the total weight of edges predicted to be in the min-cut. These ratios are denoted with $\\eta$ for false negatives (where $\\eta \\in [0,1]$) and $\\rho$ for false positives (where $\\rho$ could be arbitrarily large).  \n\nThe authors also show how effective prediction vectors can be learned from a distribution over graphs with a sample of polynomial size (hence establishing PAC guarantees for random graphs).\n\nEmpirically, the proposed algorithm demonstrates speedups over the classical Karger algorithm, even when predictions are moderately noisy. The experimental evaluation includes tests on synthetic graphs, minimum cut instances derived from TSP LP relaxations, and real-world graph datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful comments and suggestions. We would like to highlight the following points:\n+ **Knowing parameters:** Our theoretical guarantees indeed assume knowledge of $\\rho, \\eta$. However, the same analysis applies when only upper bounds on these parameters are available: simply replace $\\rho, \\eta$ in the analysis with those upper bounds. We will add a discussion in the paper clarifying that the results remain valid under this relaxed assumption.\n+ **Comparing to other cut algorithms:** This paper is the first to demonstrate how learned predictions can speed up global min-cut algorithms, providing a proof of concept for this new direction. While advanced deterministic or near-linear-time algorithms (e.g., Henzinger et al. (SODA 2024)) exist, they often involve overheads that limit their usability in practice. In fact, as we point out on page 2, due to such overheads, the two most popular network algorithm libraries implement minimum cut algorithms which in theory are far slower. In contrast, Karger’s algorithm remains popular in many graph libraries due to its simplicity and strong parallelization potential. By incorporating learned predictions into Karger’s and Karger-Stein’s algorithms, we show how one can achieve meaningful runtime improvements in realistic settings without sacrificing their desirable practical properties. We will further expand on this point in the final version, highlighting the potential for future extensions of this prediction-augmented framework to other cut algorithms.\n+ **Parallelism:** Karger’s algorithm (and, by extension, our Boosted Karger variant) is known for its high parallelizability, making it appealing for large-scale distributed settings. We will emphasize in the revised manuscript that Henzinger et al. (SODA 2024), while state-of-the-art in terms of asymptotic complexity, does not share the same level of parallelization potential. This distinction underscores one advantage of our learning-augmented framework.\n+ **Runtime of Boosted Karger vs Boosted FPZ:** We remark that one theorem refers to the success probability and the other refers to the run time. Therefore, the net runtime of Boosted Karger’s under the requirement that it succeeds with constant probability is $O(n^{2\\eta}\\rho^{2(1-\\eta)}m)$, since each trial of Karger’s takes $O(m)$ time. Thus, mirroring comparisons between Karger’s and Karger-Stein, Boosted FPZ is always better in terms of sequential runtime. However, Boosted Karger’s like the original Karger’s remain highly parallelizable. We will be happy to make this point explicitly upon revision.", "claims_and_evidence": "Yes, the main claims of the paper are supported by clear and convincing evidence. The theoretical results are proven and establish how prediction accuracy—quantified through false-positive and false-negative ratios—impacts the success probability and runtime of the modified algorithms. The framework is carefully analyzed for both Karger’s and the Karger-Stein algorithms (via the FPZ framework).", "methods_and_evaluation_criteria": "Yes, I find the proposed methods and evaluation criteria to be appropriate. The paper focuses on improving the runtime of classical global minimum cut algorithms using predictions, and the evaluation criteria are natural and well-justified. The experimental inputs include synthetic graphs, structured instances derived from TSP LP relaxations, and real-world graph datasets, which are reasonable benchmarks in combination. Together, the methods and evaluation setup effectively support the paper’s goal of combining theoretical improvement with empirical applicability.", "theoretical_claims": "Yes, I checked the structure and reasoning of the key theoretical results. The arguments seem correct to me, and the proofs follow standard techniques in randomized algorithm analysis. I also reviewed the use of false-positive and false-negative rates in the survival probability analysis and found the reasoning to be clear and interesting. While I did not verify every step in full detail, I found no issues in the high-level logic or conclusions in the proofs.", "experimental_designs_or_analyses": "Yes, I reviewed the experiments, which mainly compare the proposed prediction-augmented Karger algorithm to the classical Karger’s algorithm without prediction across a range of instances. The evaluation criteria and results are appropriate and aligned with the theoretical claims.\n\nHowever, a notable limitation is that the experimental results focus exclusively on the prediction-augmented variant of Karger’s algorithm, while the theoretical analysis also covers the  Boosted FPZ algorithm (which is absent in the experiments). Including experiments for the latter would have improved the experiments. In addition, all graphs in the experiments are unweighted, while I believe the weighted case, where weights are highly skewed, is more aligned with worst-case scenarios. Finally, while less critical, it would have been helpful to include comparisons against recent state-of-the-art algorithms for global minimum cut, such as the algorithm by Henzinger et al. (SODA 2024).", "relation_to_broader_scientific_literature": "The contributions of this paper lie at the intersection of classical randomized algorithms for graph problems and the more recent field of learning-augmented algorithms, which has attracted significant attention in recent years. The paper builds upon Karger’s algorithm for global minimum cut and the FPZ algorithm of Fox et al. (SODA 2019), which extends the Karger-Stein approach. The main novelty is the introduction of prediction-guided edge contraction, where edge weights are adjusted based on predicted cut membership, and a rigorous analysis of how this modification affects the algorithm’s success probability and runtime. Given the foundational importance of the minimum cut problem in both theory and practice, this contribution is valuable.\n\nThe work can also be compared to the recent improvements in exact global min-cut algorithms, such as the algorithm by Henzinger et al. (SODA 2024), which represents the current state of the art. While those advances focus on intrinsic algorithmic improvements, this paper explores a complementary direction—namely, runtime acceleration via auxiliary prediction information.\nThat said, the paper could be strengthened by providing a theoretical comparison between the two boosted algorithms presented (i.e., the boosted Karger and boosted FPZ variants), as well as a theoretical and empirical comparison with recent state-of-the-art algorithms without predictions.\n\nFinally, the paper connects conceptually to the broader literature on algorithms with predictions, particularly the line of work initiated by Lykouris and Vassilvitskii (2021) and others, which studies performance guarantees under prediction errors. However, unlike most work in this domain, this paper does not offer formal robustness guarantees, which is an important issue that could be acknowledged and discussed more clearly.", "essential_references_not_discussed": "I did not identify any missing references essential to understanding the paper's contributions. Recent work in exact minimum cut algorithms, in particular, the algorithm by Henzinger et al. (SODA 2024), represents the current state-of-the-art algorithms without predictions. Although this paper is orthogonal in motivation, adding a short note about its details would help place the proposed contributions in a broader context.", "other_strengths_and_weaknesses": "- One potential weakness, which is acknowledged in the paper, is that the proposed algorithm requires knowledge of the prediction error parameters, particularly the false-positive ratio $\\rho$, to set the threshold parameter $t$ for the theoretical results to hold. \n\n- The algorithms are not robust in the following sense. The false positive ratio $\\rho$ can be arbitrarily large (it is decided by the weight of the edges that is not bounded as a function of $n$). If one knows $\\rho$, which is somehow assumed (see the point above), the algorithm can become robust by ignoring the predictions when $\\rho$ is high. But I think knowledge of $\\rho$ is not given in adversarial scenarios (maybe one can justify an upper bound for $\\rho$.\n\n- Experiments only consider the Boosted Karger algorithm and the unweighted graphs.", "other_comments_or_suggestions": "- Consider adding two plots to illustrate how the theoretical performance of the two algorithms compares. In one plot, you could fix $\\rho$ (the false-positive rate) and vary $\\eta$ (the false-negative rate); in the other, fix $\\eta$ and vary $\\rho$. This would help compare the two algorithms, visualize the trade-offs, and provide clearer insight into the relative strengths of the two approaches.\n\n- Add a note on how the algorithms can become robust if $\\rho$ is known (see above).\n\n- As a minor writing suggestion, some of the notation and variable names in the theoretical sections (e.g., survival probabilities, prediction error parameters) could be introduced more formally, with additional intuitive explanations to improve readability and accessibility.\n- Consider rewriting Theorems 1.1 and 1.2 in a more consistent form, possibly expressing both results in terms of running time, to make the comparison between the two algorithms clearer and easier.", "questions_for_authors": "1- Can similar theoretical results be obtained if the values of $\\rho$ and $\\eta$ are unknown, but upper bounds on them are available? If so, it would be helpful to include a brief discussion of this scenario in the paper.\n\n2- One motivation for augmenting Karger’s algorithm and its variants with predictions is that they are highly parallelizable and thus attractive for practical use. Is it correct that the algorithm of Henzinger et al. (SODA 2024) is not similarly parallelizable? If so, this distinction could be highlighted more explicitly to strengthen the motivation for your approach.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: The submission presents an improved version of the Karger-Stein algorithm with prediction-guided edge contraction. The theoretical contribution is very interesting and contains relevant novel ideas. Empirically, the proposed algorithm demonstrates speedups over the classical algorithm, even when predictions are moderately noisy. Overall, I consider this to be a strong contribution to ICML.
Decision: Accept (poster)