Skip to content

Flow Ladder

This ladder should build the instinct that maximum flow is mostly about modeling: once the right network is built, Dinic is often the straightforward part.

Inside the repo, the tutorial-first bridge page for this whole family is Maximum Flow.

Who This Is For

Use this ladder if:

  • flow still feels like a black box
  • node splitting and cut interpretations are not yet automatic
  • you want to know when flow is the right reduction and when it is overkill

Warm-Up

  • classic max flow
  • edge-disjoint path reductions

Target skill:

  • trust the residual-network model and reverse edges

Core

Target skill:

  • translate capacity statements into a correct network

Stretch

Transition note:

  • Maximum Flow (Push-Relabel) is the clean sibling rep where the model stays identical but the engine shifts from blocking-flow augmenting paths to preflow, heights, excess, and the gap heuristic
  • Minimum Cut is the clean handoff from one source-sink cut worldview into the dedicated Randomized / Global Min-Cut lane, where the graph is still undirected but there is no designated pair
  • MCQUERY is the clean handoff from one max-flow/min-cut instance into the dedicated Gomory-Hu ladder, where repeated cuts are compressed into one tree
  • Reactor Cooling is the clean handoff from plain max flow into lower / upper bounds -> feasible circulation
  • MINCOST is not just “Dinic with costs”; it switches to a min-cost-flow engine with shortest augmenting paths, reduced costs, and potentials

Target skill:

  • see flow as a modeling language, not just one algorithm
  • recognize when the source/sink pair disappears and the right next stop is global min-cut
  • spot when lower bounds turn plain Dinic into a reduction step rather than the full solution
  • recognize when a whole family of min-cuts can be compressed into one tree

Retrieval Layer

Exit Criteria

You are ready to move on when:

  • you can explain why reverse edges exist
  • you can spot vertex-capacity problems and apply node splitting
  • you can tell whether matching or flow is the cleaner reduction

External Practice