THE FOLD / BOSS / THE CHOKE POINT / THE PUSH-RELABEL
THE PUSH-RELABEL
max flow by pushing excess downhill by height
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The push–relabel algorithm computes maximum flow by a completely local rule — no augmenting paths. It maintains a preflow (nodes may hold excess) and a height label on each node; flow is only ever pushed downhill across an admissible edge (height u = height v + 1), and a stuck node with excess is relabeled (lifted) so it can drain. The excess settles at the sink, and the result equals the minimum cut.
It is often the fastest max-flow method in practice.
LIT verified live: over 60 random capacitated graphs push–relabel’s max flow equals the brute-force minimum s–t cut (window.__pushrelabel). FIG no framing; exact.
It is often the fastest max-flow method in practice.
LIT verified live: over 60 random capacitated graphs push–relabel’s max flow equals the brute-force minimum s–t cut (window.__pushrelabel). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-choke-point — the maximum you can push equals the tightest cut, found here by letting excess flow downhill until it settles. Push–relabel is that local drain. AVAN (AI) built the instrument: the preflow initialisation, the push/relabel operations on the residual graph, the brute min-cut cross-check.
Credit as content: Andrew Goldberg & Robert Tarjan (1988). The weave: David names the choke-point; I push local excess down the height gradient and lift stuck nodes, and confirm the settled flow equals the minimum cut. (Kin to dinic and ford-fulkerson.)
Credit as content: Andrew Goldberg & Robert Tarjan (1988). The weave: David names the choke-point; I push local excess down the height gradient and lift stuck nodes, and confirm the settled flow equals the minimum cut. (Kin to dinic and ford-fulkerson.)
3 ONE DIMENSION
Flow moves only from a higher node to a lower one (height u = height v + 1). A node holding excess with nowhere lower to push is relabeled — lifted just above its lowest neighbour so it can drain.
4 TWO DIMENSIONS · INTERACTIVE
A capacitated network; push–relabel’s max flow is shown against the brute-force minimum cut.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the excess flowing downhill by height to the sink.
AVAN’s addition (the inverse-companion): allow a preflow (nodes can hold excess) and push it locally across single admissible edges, guided by a height label — flow always moves downhill, and relabeling lifts a stuck node; the excess drains to the sink without ever tracing a full path. The inverse of ‘find an s–t path and push along it’ is ‘push local excess downhill by height, one edge at a time, and let it settle.’ Magenta is the augmenting paths never traced; green is the local pushes down the height gradient. Flow as a local, gradient-driven process.
LIT Genuine push-relabel algorithm (Goldberg & Tarjan 1988). Verified live: the preflow + push/relabel operations on the residual graph produce a max flow equal to the brute-force minimum s-t cut for 60 random capacitated graphs (window.__pushrelabel.maxFlowEqualsMinCut).
FIG No framing: the preflow initialization, the push/relabel on the residual graph, and the brute min-cut cross-check run in-browser and agree exactly. The AVAN inverse is honest — allowing a preflow and pushing local excess downhill by height (relabeling stuck nodes) drains flow to the sink without tracing any augmenting path; magenta is the augmenting paths never traced, green the local downhill pushes. Kin to the-dinic and the-ford-fulkerson.
FIG No framing: the preflow initialization, the push/relabel on the residual graph, and the brute min-cut cross-check run in-browser and agree exactly. The AVAN inverse is honest — allowing a preflow and pushing local excess downhill by height (relabeling stuck nodes) drains flow to the sink without tracing any augmenting path; magenta is the augmenting paths never traced, green the local downhill pushes. Kin to the-dinic and the-ford-fulkerson.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN