Flows & Matching

The polynomial half of the hard problems. Coloring & Covering ended on a cliff - independent set, clique, vertex cover, all NP-hard on a general graph. This page is the other side: matching and minimum cut are both polynomial, both reduce to the same algorithm, and between them they make a surprising number of "assign these to those" and "what is the bottleneck" problems tractable.

The practical value is almost entirely in recognising the reduction. Writing max-flow from scratch in an interview is rare; noticing that a scheduling or assignment problem is max-flow is the skill.

1. Flow networks and max flow

A flow network is a directed graph where every edge has a capacity, plus two distinguished vertices: a source s and a sink t. A flow assigns each edge an amount up to its capacity, subject to one rule - conservation: for every vertex other than s and t, what flows in must flow out. The value of a flow is the total leaving s. Max flow asks for the largest possible value.

Water through pipes.

Capacities are pipe diameters, the flow is how much water actually moves, and conservation says no vertex is a tank - water neither accumulates nor appears. Max flow is the most water the network can carry from the tap to the drain, and it is limited by the narrowest set of pipes you would have to cut to disconnect them - not by any single pipe.

The augmenting-path idea

Every max-flow algorithm is the same loop: find a path from s to t with spare capacity, push as much as that path allows, repeat until no such path exists. The one non-obvious ingredient is the residual edge: when you push f units along u -> v, you also create (or increase) a reverse edge v -> u with capacity f. Pushing flow back along it means "undo part of an earlier decision," and without that escape hatch the greedy gets stuck at a suboptimal answer.

from collections import deque

 

def max_flow(num_nodes, capacity, s, t):

# capacity[u][v] = remaining capacity, mutated in place

def bfs_augmenting_path():

parent = [-1] * num_nodes

parent[s] = s

q = deque([s])

while q:

u = q.popleft()

for v in range(num_nodes):

if parent[v] == -1 and capacity[u][v] > 0:

parent[v] = u

if v == t:

return parent

q.append(v)

return None

 

total = 0

while (parent := bfs_augmenting_path()) is not None:

# the path's bottleneck is its smallest remaining capacity

push, v = float('inf'), t

while v != s:

push = min(push, capacity[parent[v]][v])

v = parent[v]

v = t

while v != s:

u = parent[v]

capacity[u][v] -= push # consume forward capacity

capacity[v][u] += push # create the RESIDUAL edge

v = u

total += push

return total

⚠

Missing capacity[v][u] += push fails silently

Omit capacity[v][u] += push and the algorithm returns a wrong answer without ever failing. The residual edge is what makes the greedy provably optimal - it is the only way a later augmenting path can route flow around an earlier bad choice. On the classic 4-vertex example (s->a, s->b, a->b, a->t, b->t, all capacity 1 except a->b) the greedy first picks s->a->b->t, and only a residual push back along b->a lets it reach the true answer of 2.

Mnemonic

Finding augmenting paths with BFS (shortest first) is Edmonds-Karp, O(V * E^2); with DFS it is Ford-Fulkerson and may not even terminate on irrational capacities. Use BFS. The shortest-augmenting-path rule is what turns "repeat until stuck" into a polynomial bound.

2. Max-flow min-cut

An s-t cut partitions the vertices into two sets with s on one side and t on the other; its capacity is the total capacity of the edges crossing from the s side to the t side. The max-flow min-cut theorem says these two numbers are always equal:

The maximum flow from s to t equals the minimum capacity of an s-t cut.

One direction is obvious: every unit of flow must cross every cut, so flow can never exceed any cut's capacity. The other direction is what the algorithm proves: when no augmenting path remains, the set of vertices still reachable from s in the residual graph is one side of a cut whose every crossing edge is saturated - so that cut's capacity equals the flow you found.

Mnemonic

Max flow is the answer; min cut is the reason for the answer. They are the same number seen from opposite sides - one says "this much can get through," the other says "because these edges are the bottleneck." So an algorithm that computes the flow also hands you the bottleneck for free: run one last BFS from s in the residual graph, and the crossing edges are the min cut.

def min_cut_edges(num_nodes, capacity, original, s):

# call AFTER max_flow has saturated `capacity`; `original` is the untouched copy

from collections import deque

reachable = {s}

q = deque([s])

while q: # who can s still reach in the residual?

u = q.popleft()

for v in range(num_nodes):

if v not in reachable and capacity[u][v] > 0:

reachable.add(v)

q.append(v)

return [(u, v) for u in reachable

for v in range(num_nodes)

if v not in reachable and original[u][v] > 0]

⚠

Cut extraction needs the original capacities too

Extracting the cut needs the original capacities kept alongside the residual ones. max_flow mutates capacity in place, so by the time it finishes you can no longer tell "this edge was saturated" from "this edge never existed" - both read as 0. Deep-copy the capacity matrix before running the flow, or the cut you extract will be missing exactly the edges that matter.

⚠

Minimum cut is easy; maximum cut is NP-hard

Minimum cut is polynomial; maximum cut is NP-hard. These read as a symmetric pair and are nothing alike - the duality with flow exists only for the minimum. Similarly, min cut between a specific s and t is what flow gives you; "global min cut" over all pairs is a different (still polynomial) problem needing a different algorithm.

3. Bipartite matching

A matching is a set of edges no two of which share a vertex. On a bipartite graph, maximum matching is the single most reusable flow reduction there is, because it is what every "assign each of these to one of those" problem actually is.

Unit capacities force each vertex onto at most one matched edge, so max flow equals max matching.

You rarely need the full flow machinery. The direct algorithm is a DFS that tries to find an augmenting path: an unmatched left vertex looks for a right vertex that is either free, or matched to someone who can be bumped elsewhere.

def max_bipartite_matching(num_left, adj):

# adj[u] = right-side vertices u can be assigned to

match_of_right = {} # right vertex -> left vertex

 

def try_assign(u, seen):

for v in adj[u]:

if v in seen:

continue

seen.add(v)

# v is free, OR v's current partner can move somewhere else

if v not in match_of_right or try_assign(match_of_right[v], seen):

match_of_right[v] = u

return True

return False

 

return sum(try_assign(u, set()) for u in range(num_left))

⚠

The seen set must be fresh per left vertex

The seen set must be fresh per left vertex, and must live on the right side. Hoisting it outside the for u loop makes each right vertex considered at most once across the whole run, which silently under-counts the matching. Putting it on the left side instead lets the recursion revisit a right vertex and loop. One set() per try_assign call from the top, keyed on right vertices - that is the contract, and both deviations produce answers that look plausible on small inputs.

Mnemonic

"Can you move over one seat?" An augmenting path is exactly that request propagating down a chain: the newcomer asks a seated person to shift, who asks the next, until someone finds an empty seat. If the chain reaches an empty seat, everyone shifts and the matching grows by one; if it dead-ends, this newcomer genuinely cannot be seated.

The duality theorems

Bipartite graphs are where the NP-hard problems from Coloring & Covering collapse into polynomial ones, and these two theorems are why:

Theorem	Statement	What it buys
Konig's theorem	in a bipartite graph, max matching = min vertex cover	Minimum vertex cover - NP-hard in general - becomes a matching computation. With the complement identity from Coloring & Covering, maximum independent set comes free too: n - max matching.
Hall's marriage theorem	a perfect matching saturating the left side exists iff every subset S of the left has |neighbours(S)| >= |S|	A certificate of impossibility: when no perfect matching exists, there is a specific left subset with too few neighbours to blame, which is what "why is this schedule infeasible" questions want.
Dilworth / min path cover	in a DAG, the minimum number of paths covering every vertex = n - max matching in a derived bipartite graph	Turns "fewest chains/servers/pipelines to cover all tasks" into matching. The derived graph splits each vertex into an out-copy and an in-copy.

⚠

Bipartite theorems don't hold on general graphs

These theorems are bipartite-only, and the general-graph versions are false. Maximum matching on a general graph is still polynomial (Edmonds' blossom algorithm), but max matching no longer equals min vertex cover, and Hall's condition no longer characterises anything. If a problem's graph is not bipartite, check that first - it is the load-bearing hypothesis, and it is also usually the thing the problem is quietly telling you by splitting the input into two kinds of thing.

4. Recognising the reduction

This is the part worth memorising. Flow problems in the wild almost never say "flow."

Problem shape	The reduction
"Assign each worker to at most one task"	Bipartite matching. Workers left, tasks right, an edge per eligible pair.
"Each worker can take up to k tasks"	Same, but the source-to-worker edge gets capacity k instead of 1. This is why the flow formulation is worth knowing even when plain matching would do - capacities generalise where matching does not.
"Minimum number of X covering every Y"	Minimum vertex cover, so on a bipartite graph: max matching (Konig).
"Maximum set with no two conflicting"	Maximum independent set, so on a bipartite graph: n - max matching.
"Fewest paths/chains to cover all tasks"	Minimum path cover on a DAG: n - max matching on the split graph.
"What is the bottleneck / cheapest set of links to sever"	Minimum cut, so max flow.
"Choose a subset to maximise profit minus penalties"	Project selection / max-closure, solved as a min cut with infinite-capacity dependency edges.
Grid problems: "place non-attacking pieces", "cover with dominoes"	Colour the grid like a chessboard - it is bipartite by construction, so matching applies. Domino tiling is perfect matching.

Mnemonic

Two sides plus "at most one each" means matching; capacities or "at most k each" means flow; "cheapest thing to break" means min cut. Those three tells cover nearly every flow problem that shows up outside a competitive-programming contest.

A grid graph - cells adjacent to their four neighbours - is always bipartite, and the proof is the chessboard: colour cell (r, c) by the parity of r + c, and every edge necessarily joins opposite parities, because a step changes exactly one coordinate by one. So no grid graph has an odd cycle, which means every grid problem of the form "pair up adjacent cells" or "pick cells with no two adjacent" is a bipartite matching or independent-set problem, and therefore polynomial. That is the entire reason domino-tiling and non-attacking-rook problems on grids are tractable while their general-graph versions are not.

Where to go next

• Coloring & Covering - the NP-hard problems that Konig's theorem rescues on bipartite graphs.
• Shortest Paths & Bipartite Check - how to verify the bipartite hypothesis these reductions all depend on.