Skip to main content

Bipartite Matching via Max Flow

What This Concept Is​

A bipartite matching chooses allowed left/right pairs with no repeated endpoint. Maximum cardinality asks for as many pairs as possible; maximal merely means no single additional edge can be inserted. Build source→left, left→right and right→sink edges, all with capacity one, to reduce maximum cardinality to flow.

Why It Matters Here​

A reduction needs both directions and integrality. Each matching produces a feasible unit flow per matched pair. Conversely an integral flow uses at most one allowed pair per endpoint because source/terminal capacities are one. Integer-capacity augmentations from zero give an integral maximum flow, so extracting positive pair-edge flows gives a maximum matching.

Concrete Examples​

Allowed pairs (0,0),(0,1),(1,0) admit the matching (0,1),(1,0) of size 2. Greedily choosing (0,0) first and refusing reassignment yields a maximal matching of size 1. The residual alternating path undoes that choice.

A Hall obstruction explains impossibility: if some left subset X has fewer neighbors than vertices, no matching can cover X. With left vertices a,b,c all connected only to x,y, at most two can be assigned. A flow/min-cut witness can expose such a bottleneck instead of merely saying "assignment failed".

Common Confusion / Misconceptions​

Matching does not mean weighted minimum-cost assignment or stable marriage. Preferences, utilities, worker capacities and time conflicts add different constraints. A fractional flow would not justify simply treating every positive pair edge as an assignment; the integral optimum is what makes extraction valid. Duplicated allowed pairs do not permit matching an endpoint twice.

How To Use It​

Keep left and right vertex namespaces separate even when both use integer IDs. State how original pairs map to network vertices and how the answer maps back. The lab uses Edmonds–Karp on V'=L+R+2 and E'=L+R+E, not the specialized Hopcroft–Karp O(E sqrt(V)) matching algorithm. Isolated side vertices still count in construction and any end-to-end bound.

Check Yourself​

  1. Why does a maximal matching need not be maximum?
  2. Where does integrality enter the reduction proof?
  3. How do separate side namespaces prevent vertex collisions?
  4. What changes when workers can take multiple jobs?

Mini Drill or Application​

Implement Lab E and compare all 3-by-3 bipartite edge subsets to a brute-force matching oracle. Produce a Hall-deficient subset for an impossible complete assignment. Extend to worker capacities only after changing the output contract and reduction proof. See P20.

Read This Only If Stuck​

Find bipartite matching, integrality, and Hall obstructions in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.