Why reductions are useful
Many problems that do not initially look like flow problems can be solved by constructing a maximum-flow input. The maximum-flow value and the arcs that carry flow are then translated back into a solution of the original problem.
The chapter uses this idea for matching problems. A matching decision becomes a flow through a short path:
source → student or group → advisor → sinkCapacities enforce the rules. For ordinary bipartite matching, each student and advisor can be used at most once. For ENGRG 1050, a student-group node can send as many units as the group size, and an advisor node can receive as many units as the course capacity.
Reduction pipeline
allowed student–advisor pairs, group sizes, advisor capacities
directed arcs, source, sink, capacities
matched pairs or assigned numbers of students
Role of integrality
When all capacities are integers, maximum flow has an integral optimum. This is what turns flow values into discrete matching decisions.
Application 1: Bipartite matching
The motivating problem is to match students to advisors. Not every student–advisor pair is allowed: each student lists potential advisors, and each advisor can be matched to at most one student. The goal is to match as many students as possible.
Chapter example
| Student | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Potential advisors | a, b | a, c | a, b, d | c, d | c, e, f | d, e, f |
1. Add source arcs
For every student i, add an arc (s,i) with capacity 1. This lets each student be matched at most once.
2. Add preference arcs
For every allowed pair, add an arc from the student to the advisor. Its capacity can be treated as ∞, because the source and sink arcs already limit the flow.
3. Add sink arcs
For every advisor j, add an arc (j,t) with capacity 1. This lets each advisor be matched at most once.
Correctness idea
An integral flow of value k gives a matching of size k: match student i to advisor j exactly when the flow on arc (i,j) is 1. Conversely, any matching of size k creates a feasible flow of value k. Therefore a maximum flow gives a maximum matching.
Interactive lab: maximum bipartite matching
Toggle allowed pairs, then step through the max-flow computation. Thick green arcs carry flow. A blue path is the most recent augmenting path. When no augmenting path remains, the reachable set in the residual graph becomes the minimum-cut certificate.
Allowed pairs
Check a box when the student can be matched to that advisor.
Algorithm controls
The chapter displays one possible maximum matching. A max-flow algorithm may find a different maximum matching with the same value.
Flow-network reduction
not solvedCurrent matching
What the minimum cut tells us
If not all students can be matched, the maximum-flow value is less than the number of students. By the max-flow/min-cut theorem, there is also a cut of capacity less than the number of students.
In this reduction, a finite minimum cut cannot pay for an ∞-capacity student-to-advisor arc. Therefore, when a student is on the source side S, all of that student's listed advisors must also be on S.
The only finite arcs crossing from S to T are source-to-student arcs for students in T, and advisor-to-sink arcs for advisors in S. In the ordinary matching case:
capacity(S,T) = |T ∩ B| + |S ∩ A|Since |B| = |T ∩ B| + |S ∩ B|, a cut with capacity below |B| implies:
|S ∩ A| < |S ∩ B|Interpretation
The cut identifies a set of students that collectively have too few compatible advisors. This is the same obstruction expressed by Hall's condition, obtained here directly from the flow model.
Use the “Remove d from 3,4” preset in the lab above. After running to optimality, the highlighted set shows students 1,2,3,4 with only advisors a,b,c available on the source side: four students competing for three advisors.
Application 2: ENGRG 1050 matching
The second application uses the same reduction pattern, but the units of flow are now individual students inside student groups. Each group has a size, and each advisor can teach a course with at most 18 students in the chapter example.
Chapter example
| Student group | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Potential advisors | a, b | a, c | a, b, d | c, d | c, e, f | d, e, f |
| Group size | 15 | 10 | 20 | 30 | 20 | 10 |
Modified capacities
The only change from ordinary matching is on the outside arcs. Set u(s,i) equal to the number of students in group i, and set u(j,t) equal to advisor j's teaching capacity. The middle arcs still represent compatibility and can be assigned capacity ∞.
Group sizes
Advisor capacities
Compatibility
Algorithm controls
ENGRG flow network
not solvedCurrent assignment
Chapter obstruction
For the chapter data, groups 1,2,3,4 contain 15+10+20+30=75 students. Their compatible advisors on the source side of the minimum cut are a,b,c,d, with total capacity 4×18=72. At least 3 students cannot be assigned under those constraints.
Takeaways
Flow values encode decisions
A unit on a student-to-advisor arc means that the corresponding assignment is made. In group matching, the number on the arc is the number of students assigned that way.
Capacities encode rules
Source capacities limit what each student or group can send. Sink capacities limit how much each advisor can receive.
Min cuts explain failure
If the max flow is too small, the min cut gives a compact certificate: a set of demand nodes whose compatible supply nodes do not have enough capacity.
