Skip to content

Global Min-Cut Hot Sheet

Use this sheet when the graph is undirected, there is no designated source/sink, and the statement wants the cheapest cut that disconnects the graph in any nontrivial way.

Do Not Use When

  • one explicit s-t cut or throughput question matters -> Flow hot sheet
  • many pairwise min-cuts on the same graph matter -> Gomory-Hu hot sheet
  • the graph is directed
  • costs or lower bounds dominate more than the cut family itself

Choose By Signal

  • one undirected weighted graph, no source/sink, minimum disconnect cost -> Randomized / Global Min-Cut
  • one designated s-t cut / throughput / cut certificate -> Flow hot sheet
  • many pairwise undirected min-cuts compressed into one tree -> Gomory-Hu hot sheet
  • you specifically want the randomized contraction worldview after the deterministic route is already clear -> reopen the topic page and jump to the Karger / Karger-Stein compare section

Core Invariants

  • each Stoer-Wagner phase grows a set by maximum adjacency
  • the last vertex of the phase gives one minimum s-t cut in the current contracted graph
  • after merging the last two phase vertices, any better global cut must still survive in the contracted graph
  • the answer is the minimum phase cut seen across all contractions

Main Traps

  • guessing one pair (s, t) and pretending that is enough
  • forgetting the graph must be undirected
  • overwriting parallel edges instead of accumulating them
  • assuming the witness side is unique

Exact Starter Route

Reopen Paths