Research map / Learning theory and algorithms / Combinatorial and search optimization
Faster Global Minimum Cut with Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Warm-starts Karger's and Karger-Stein global minimum cut algorithms with edge predictions by reweighting likely non-cut edges to be contracted first, giving near-linear time under good predictions and robustness to errors.
Problem
Global minimum cut is solved repeatedly on similar instances, but standard randomized algorithms (Karger, Karger-Stein) discard information from prior instances; the question is how learned edge predictions can speed them up with error robustness.
Approach
Predict per-edge membership in the minimum cut, then boost weights of predicted non-cut edges so random contractions preferentially remove them, keeping the minimum cut alive; false negatives and false positives are measured separately (eta, rho) and the analysis extends to Karger-Stein via a boosted FPZ variant with a switching threshold.
Key results
- On synthetic graphs, Boosted Karger's outperforms Karger's by about two orders of magnitude when eta <= 0.5 and rho in {0,10}, and by one order of magnitude for rho=100 with eta in [0,0.6].
- Theory: Boosted Karger's success probability is Omega(1/(n^{2eta} rho^{2(1-eta)})), better than Karger's Omega(1/n^2) whenever rho = o(n).
- Theory: Boosted FPZ runs in O(m^{1-eta} n^{2eta} log n) time when rho=O(sqrt(m)) and outputs a minimum cut with probability Omega(1/log n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use edge predictions to reweight contractions | Karger on synthetic bipartite graphs · Synthetic bipartite graphs (n = 600, k = 100, ℓ = 10); η ≤ 0.5 and ρ ∈ {0, 10} | trials to find minimum cut: two orders of magnitude | Helped |
| Use edge predictions to reweight contractions | Karger on synthetic bipartite graphs · Synthetic bipartite graphs; ρ = 100 and η ∈ [0, 0.6] | trials to find minimum cut: one order of magnitude | Helped |
| Predict edges with fractional weights as minimum-cut edges | Karger on TSP LP minimum-cut instances · TSP LP minimum-cut instances | iterations to find minimum cut: order-of-magnitude improvement | Helped |
| Form predictions from sampled edges and parallel Karger runs | Karger on three real graph datasets · Three real graph datasets | trials to find minimum cut | Helped |
Surprising findings
- Predictions can remove an entire factor of n from Karger's runtime, so speedup grows with instance size even for fixed prediction quality.
- Boosted Karger's remains no worse than standard Karger's even when predicted non-cut edges are almost n times the minimum cut size, since false positives are cheap.
Limitations
- Theoretical guarantees require knowledge of eta and rho (or upper bounds); experiments use problem-agnostic parameters.
- Learning-to-predict sample complexity scales with 1/C_min and poly(n).
- Known near-linear deterministic algorithms are impractical; the paper's advantage is in randomized Karger-style settings.
Experimental setup
Datasets: synthetic bipartite random perfect-matching graphs random TSP subtour LP instances three real graph datasets (unspecified in text)
Benchmarks: synthetic bipartite graphs (n=600) TSP subtour LP min-cut instances (n=500) three real graph datasets
Metrics: number of trials/repetitions to find minimum cut number of iterations
Baselines: Karger's algorithm Karger-Stein algorithm FPZ
Builds on: Karger's algorithm Karger-Stein algorithm FPZ hypergraph min-cut algorithm
Closest papers by meaning
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.88)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.86)
- Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.86)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.86)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.85)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.