Algorithms / Bipartite Matching Depth
Least You Need to Know: Bipartite Matching, Augmenting Paths, and Assignment Structure
Bipartite matching pairs vertices from two sides without reuse. The central progress idea is an **augmenting path**: alternating matched and unmatched edges that increases the matching size by one.
The least you need to know
- A matching is a set of edges with no shared endpoints.
- Bipartite graphs split vertices into two sides with edges only across the split.
- Maximum matching searches for the largest possible set of disjoint pairings.
- Augmenting along an alternating path flips matched/unmatched status and increases the matching size.
- Many assignment and scheduling problems reduce to bipartite matching.
Key notation
matching
set of pairwise endpoint-disjoint edges
augmenting path
alternating path starting and ending at unmatched vertices
maximum matching
matching of largest possible size
Tiny worked example
- Suppose left vertices are jobs and right vertices are workers.
- A current matching might leave one job unmatched.
- If an alternating path reaches an unmatched worker, flipping that path matches one more job overall.
- That is the key local move behind augmenting-path algorithms.
Common mistakes
- A maximum-cardinality matching is not the same as a minimum-edge-cover question.
- Edges in a matching cannot share endpoints.
- The augmenting-path theorem applies to matchings, not arbitrary path sets.
How to recognize this kind of problem
- You are assigning one side's items to another side without reuse.
- The graph is naturally split into left and right parts.
- Alternating/augmenting paths or Hall-style feasibility ideas appear.