Skip to content

Gomory-Hu Ladder

This ladder is for the first time a cut problem says:

  • many vertex pairs matter
  • direct repeated max-flow is too expensive
  • the graph is undirected, so one cut tree can compress the whole family

It is intentionally narrow:

  • one exact starter
  • one flagship solved rep
  • strong compare points back to plain flow

Who This Is For

Use this lane if:

  • Maximum Flow already feels comfortable for one s-t cut
  • residual reachability after max flow already makes sense
  • your next problem is no longer about one cut, but about many cuts on the same undirected graph

Warm-Up

  • one max flow / min cut -> FFLOW
  • explicit cut certificate -> Police Chase
  • one global undirected cut before the pairwise layer -> Minimum Cut

Target skill:

  • explain clearly why the new problem is not "just run Dinic for every pair"

Core

  • cut tree on the same vertex set
  • n - 1 max-flow calls
  • residual reachable side drives reparenting
  • exact starter route: gomory-hu-tree.cpp
  • flagship solved rep: MCQUERY

Target skill:

  • turn "many pairwise min cuts" into "build one weighted tree, then solve a tree problem"

Stretch

Target skill:

  • know when the exact starter still fits and when the real difficulty has moved into the query layer after the tree is built

Retrieval Layer

Repo Anchors And Compare Points

Exit Criteria

You are ready to move on when:

  • you can say why the graph must be undirected
  • you understand why n - 1 cuts are enough
  • you can explain why residual reachability after max flow changes the parent structure
  • you can reduce one pairwise-cut aggregation problem to tree edges plus one second structure

External Practice