Skip to content

Push-Relabel Hot Sheet

Use this page when the model is still plain static s-t maximum flow, but you want a non-augmenting-path engine instead of reopening Dinic first.

Do Not Use When

Choose By Signal

  • plain max flow / min cut, moderate network, default augmenting-path route -> dinic.cpp
  • plain max flow / min cut, but you want a height/excess preflow engine or a denser hard-benchmark fallback -> push-relabel-max-flow.cpp
  • one cut certificate after the flow finishes -> solve max flow first, then reopen Flow hot sheet

Core Invariants

  • a preflow may violate conservation at internal nodes; only s and t are exempt from the final conservation story
  • an admissible push uses a residual edge with height[u] = height[v] + 1
  • relabel only happens when no admissible residual edge remains
  • if one height layer disappears, the gap heuristic can kill every higher active layer on the source side

Main Traps

  • expecting internal conservation to hold during intermediate states
  • forgetting that reverse residual capacity must still be updated on every push
  • pushing source or sink back into the active structure
  • mixing this engine with lower-bounded or costed flow models as if the same starter already handled them

Exact Starter Route

Reopen Paths