Modeling is a reduction in disguise
The previous four guides handed you a complete toolkit: a flow network with capacities, the engine of augmenting paths and the residual graph, the max-flow min-cut theorem, and the worked case of bipartite matching. This last guide is about a skill, not a new algorithm. When you face a brand-new problem — assigning shifts, choosing projects, routing data — the win is to recognize that it is secretly a flow problem, build the network, run a max-flow algorithm you already trust, and read the answer back out.
This is exactly a reduction in the sense you will meet again in the complexity rung: a polynomial-time transformation that turns instances of problem A into instances of problem B so that solving B answers A. Matching was the first example — there the transformation was almost transparent. Modeling generalizes that move. The art has two halves you must always supply and then justify: a construction (how the words become vertices, edges, and capacities) and a correspondence (a proof that a max flow in your network maps back to an optimal solution of the original problem, and vice versa).
The four standard gadgets
Most flow models are assembled from a small vocabulary of reusable pieces, called gadgets. The first is the super-source and super-sink. When a problem has many starting points (say five warehouses) or many endpoints (say eight stores), you cannot have several sources, because flow is defined for a single s and t. The fix: add one super-source S with an edge into each real start, and one super-sink T with an edge out of each real end. Capacities on those edges encode supplies and demands — an edge S -> warehouse of capacity 10 means 'this warehouse can ship at most 10.'
The second gadget answers a question students always ask: capacities live on edges, so how do I limit how much passes through a vertex? The trick is vertex splitting. Replace a vertex v by two copies, v_in and v_out, with a single internal edge v_in -> v_out whose capacity is the vertex's limit; redirect all edges that entered v to v_in and all that left v to v_out. Now any flow through v is forced across that one internal edge, so the vertex capacity is honored. This tiny move quietly unlocks a huge class of problems — anything where the bottleneck is a place, not a connection.
The third is unit capacities for counting. Setting an edge's capacity to 1 turns 'how much flow' into 'how many things,' because integer max-flow on integer capacities returns an integer flow (the integrality property you met in the matching guide). A bipartite matching is exactly this: capacity-1 edges from S to each left node, capacity-1 edges from each right node to T, and the value of the max flow counts matched pairs. The fourth, lower bounds and costs, is where you graduate to min-cost max-flow: attach a per-unit price to each edge and ask not just for the largest flow but the cheapest largest flow — the right model when assignments have differing qualities or distances.
A worked model: scheduling jobs to machines
Let us model one problem end to end. You have jobs and machines; each job needs a fixed amount of processing, each machine has a capacity (hours available), and a job may run on a machine only if that machine has the right tooling. Can every job be fully scheduled? This is more than matching, because a job can be split across machines and a machine serves many jobs — but the gadgets above handle it cleanly.
- Build the network: a super-source S, one vertex per job, one vertex per machine, and a super-sink T. Add S -> job with capacity equal to that job's required hours, and machine -> T with capacity equal to that machine's available hours.
- Add a job -> machine edge (capacity infinity, or just the job's hours) exactly when that machine can run that job. These edges carry the actual assignment; an infinite cap means the only real limits are the job's demand and the machine's supply.
- Run any max-flow algorithm — Edmonds-Karp or Dinic — from S to T. The value of the max flow is the total job-hours that can be scheduled.
- Read the verdict: every job is fully schedulable if and only if the max flow saturates every S -> job edge, i.e. the value equals the sum of all job demands. The flow on each job -> machine edge tells you exactly how many hours of that job to run on that machine.
The correspondence is what makes this a proof, not a hope. Any legal flow obeys conservation, so the hours flowing into a job from S equal the hours flowing out to machines — that is a valid split of the job. Capacities on machine -> T edges guarantee no machine is overbooked. Conversely, any valid schedule defines a legal flow of the same value. So max flow equals max schedulable hours, and the saturation test is exact. When some jobs cannot be fully placed, the min cut even tells you why: the saturated cut edges pinpoint the bottleneck set of machines that are oversubscribed.
Min-cut as a modeling tool: project selection
Some problems are not really about moving anything — they are about partitioning a set into two groups under conflicting pressures. For these, the right half of the duality is the hero: you model so that the minimum cut is the answer. The classic example is project selection (also called the maximum-weight closure problem). Each project earns a profit but may require buying expensive equipment; some projects depend on others. Choose a subset of projects to maximize net profit, respecting all dependencies.
The model is a small marvel. Put a vertex per project. From S, draw an edge of capacity equal to its profit into every profitable project; from every costly item draw an edge of capacity equal to its cost to T. For each dependency 'project A needs item B,' add an edge A -> B of infinite capacity. Now a finite s-t cut can never sever an infinite dependency edge, so any cut of finite capacity automatically respects every dependency. The set S-side of the minimum cut is exactly the profit-maximizing selection, and the maximum net profit equals (total profit) minus (min-cut capacity). The infinite edges are a gadget that forbids illegal partitions by making them infinitely expensive.
Notice the shift in viewpoint. In scheduling we maximized flow; here we minimized a cut, and the max-flow min-cut theorem lets one algorithm serve both — you compute the min cut by computing the max flow and reading the reachable set, just as the earlier guides showed. Image segmentation (foreground vs background) and many 'separate two classes while paying for broken affinities' problems follow the very same closure template. Recognizing whether your problem wants the flow side or the cut side of the duality is the single most useful instinct in this whole subject.
Where the flow trick stops working
Honesty matters here as everywhere on this ladder. Flow is powerful precisely because it stays in polynomial time, and that buys you a sharp boundary: many close cousins of these problems are NP-hard, and no flow model can rescue them. Bipartite matching is poly-time, but general (non-bipartite) matching needs a different, harder algorithm. Worse, asking for an integer multi-commodity flow — several distinct goods sharing the same network, each with its own source and sink — is NP-hard, even though single-commodity integer flow is easy. The integrality property that makes single-commodity flow so clean simply does not extend.
There is a beautiful exception that shows where the line falls. On bipartite graphs, finding a minimum vertex cover is poly-time and equals the maximum matching size — that is König's theorem, itself a corollary of max-flow min-cut. But on general graphs minimum vertex cover is NP-hard, and the best we have is a 2-approximation. Same word, 'vertex cover'; one structure makes it a flow problem, the other puts it beyond flow's reach. The lesson is to test the structure, not the name: bipartite, single-commodity, integer, no conflicting demands — these are the load-bearing assumptions.
The recognition checklist
Step back and the whole rung clicks into a single habit of mind. Faced with a fresh problem, ask: is there something conserved that moves from sources to sinks? Are the constraints linear caps on edges or on places? Does the objective want the most you can push, or the cheapest way to separate two groups? If the answers line up, you reach for a flow model; if a subtle ingredient — many commodities, indivisible-but-conflicting choices, a general (non-bipartite) graph — breaks the template, you have likely crossed into NP-hard territory and should pivot to approximation or heuristics instead.
And always, always finish with the correspondence. Modeling is a reduction, and a reduction without a both-directions proof is just a hopeful drawing. State precisely how a max flow becomes a solution and how a solution becomes a flow of equal value; verify conservation handles your splitting, capacities encode your limits, and integrality (if you need whole answers) is guaranteed by integer capacities. Get those right and you inherit, for free, every algorithm and every guarantee from the four guides before this one.