Network Flow and Matching Clinic

Retrieval Prompts

1. State the definition of a flow network, including capacity and conservation constraints.
2. State the Ford-Fulkerson method in four lines, including the role of the residual graph.
3. Define a residual edge and explain why backward residual edges exist.
4. State the max-flow min-cut theorem in symbols and in one sentence of prose.
5. Describe the reduction from unweighted bipartite matching to max flow.
6. State Edmonds-Karp's running-time bound and the reason BFS paths give polynomial time.

Compare and Distinguish

• flow versus preflow
• augmenting path versus residual path
• S -> T cut edges versus T -> S cut edges (only the former count)
• Edmonds-Karp versus arbitrary-path Ford-Fulkerson
• unit-capacity max flow versus general max flow
• bipartite matching versus general matching

Common Mistake Check

For each statement, identify the error:

1. "I counted backward edges T -> S in the cut capacity, so my min-cut is c(S, T) + c(T, S)."
2. "Ford-Fulkerson always terminates in polynomial time."
3. "Max flow equals min cut only when the capacities are integers."
4. "Bipartite matching reduces to shortest paths."
5. "If there is no augmenting path, I haven't yet found the max flow - I just need to try another DFS order."
6. "Hopcroft-Karp works because bipartite graphs have no cycles."

Worked Derivations

1. Prove |f| <= c(S, T) for any flow f and cut (S, T): start from the definition of |f|, sum over edges crossing the cut, apply capacity bounds.
2. Derive why the set of vertices reachable from s in the residual graph of a max flow is one side of a min cut.
3. Explain in writing why the max-flow value on the bipartite matching reduction equals the matching size.

Modeling Drill

For each problem, state the flow network (V, E, s, t, c) explicitly, then describe how to read the solution off the max flow:

1. Given n applicants and m jobs with a bipartite compatibility graph, compute the maximum number of compatible assignments.
2. Given a directed graph with s and t, compute the minimum number of edges whose removal disconnects t from s.
3. Given n projects each with a profit (possibly negative) and precedence dependencies, select a subset maximizing total profit (project-selection).
4. Given a 2D pixel grid with per-pixel foreground/background scores and neighbor smoothness costs, produce an optimal binary labeling.
5. Given a set of athletes and sports each requires, decide whether a given athlete is still in contention for a championship (baseball elimination).

Implementation Drill

Build a clean Ford-Fulkerson / Edmonds-Karp implementation with:

• explicit forward and backward residual edges sharing the same edge object
• BFS-based augmenting-path search
• an API that returns both the max-flow value and one min cut

Test on the concrete example from the Max Flow concept (the 14-flow graph). Then:

• implement bipartite matching as a thin wrapper over your max flow
• verify on complete bipartite graphs (matching size equals min(|L|, |R|))
• verify on graphs without a perfect matching (matching size is smaller)

Evidence Check

This practice page is complete only if you can:

• write the Ford-Fulkerson loop from memory, including residual edge construction
• take a problem that is not obviously a flow problem (matching, project selection, min cut) and build its flow network explicitly
• state which min cut your implementation returns and why
• verify your max-flow implementation's answer by independently computing the min cut's capacity