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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Set Bits, Powers of Two, and Lowest-Bit Tricks.
Least You Need to Know: Set Bits, Powers of Two, and Lowest-Bit TricksRelated lessons
Keep going with nearby lessons in the same topic.