Skip to content

Graphs -> Randomized / Global Min-Cut

One undirected weighted graph, no designated source/sink, and the cheapest global cut found first through deterministic Stoer-Wagner phases.

  • Topic slug: graphs/global-min-cut
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 5
  • Curated external problems: 3

Microtopics

  • global-min-cut
  • stoer-wagner
  • cut-contraction
  • maximum-adjacency-order
  • undirected-cuts
  • karger-compare

Learning Sources

Source Type
Princeton GlobalMincut Course
MIT randomized algorithms minimum cut notes Course

Practice Sources

Source Type
POJ 2914 - Minimum Cut Practice
UVa 10480 - Sabotage Practice

Repo Companion Material

Material Type
Global Min-Cut hot sheet quick reference
Global Min-Cut starter route starter route
Minimum Cut note anchor note
Maximum Flow tutorial compare point
Gomory-Hu tutorial compare point

Curated External Problems

Warm-Up

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Police Chase CSES Medium Min Cut, Edge Cut, Flow S-T Min Cut; Edge Extraction Max Flow; Cut Extraction Roads; Certificate Another clean compare point: extract one cut certificate first, then move to the global family where no designated pair remains.

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Minimum Cut POJ Hard Undirected Cuts Stoer-Wagner; Dense Cut Phases Max Flow Min Cut Intuition; Undirected Weighted Graphs Stoer-Wagner; Cut Contraction Canonical global min-cut benchmark: no designated source/sink, parallel edges allowed, and the whole task is exactly the cut-family route.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Sabotage UVa Medium Min Cut, Flow S-T Min Cut; Cut Extraction Max Flow; Minimum Cut Graph Partition Warm-up compare point: still one cut-extraction task, useful before the no-source/sink global min-cut lane.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
GLOBALMINCUT Minimum Cut primary hard - Note Code

Regeneration

python3 scripts/generate_problem_catalog.py