Skip to content

Randomized / Global Min-Cut Ladder

This lane is for the first time max-flow / min-cut is clearly nearby, but the statement gives no source and sink at all.

Who This Is For

Use this lane if:

  • Maximum Flow already feels comfortable for one explicit s-t cut
  • you can extract one cut certificate from residual reachability
  • the next graph problem wants one global cut in an undirected weighted graph

This lane is intentionally narrow:

  • one exact deterministic starter
  • one flagship benchmark that is almost pure global min-cut
  • one compare route back to plain flow
  • one compare route forward to Gomory-Hu Tree

Warm-Up

Target skill:

  • explain why "no source and sink" already changes the family boundary

Core

Target skill:

  • trust the Stoer-Wagner contraction route instead of brute-force pair enumeration

Stretch

  • compare deterministic Stoer-Wagner against randomized Karger / Karger-Stein as two views of the same family
  • reopen Gomory-Hu Tree and explain why "one global cut" is still narrower than "many pairwise cuts"
  • try one warm-up s-t cut task and one global cut task back-to-back, then explain the boundary in one sentence

Target skill:

  • know when the right endpoint is:
  • plain flow
  • one global cut
  • or one cut tree

Retrieval Layer

Repo Anchors And Compare Points

Exit Criteria

You are ready to move on when:

  • you can explain why the graph must be undirected
  • you understand why the answer is the best phase cut across contractions
  • you can say exactly why this is not yet a Gomory-Hu task
  • you know where the randomized contraction worldview fits, even if the repo starter is deterministic

External Practice