Graphs -> Matching

Augmenting-path techniques for bipartite matching and reductions to cover and assignment problems.

• Topic slug: graphs/matching
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 2
• Repo companion pages: 0
• Curated external problems: 12

Microtopics

• bipartite
• augmenting-path
• kuhn
• hopcroft-karp
• konig
• assignment-reduction

Learning Sources

Source	Type
OI Wiki max bipartite matching	Reference
cp-algorithms Kuhn	Reference
OI Wiki augmenting path	Reference

Practice Sources

Source	Type
Library Checker bipartite matching	Practice
CSES Problem Set	Practice
USACO contest archive	Practice

Curated External Problems

Warm-Up

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Gopher II	UVa	Easy	Bipartite Matching, Geometry-To-Graph	Distance-Threshold Graph; Max Matching	Bipartite Matching Basics; Distance Formula	Geometry; Reachability	The archetypal geometry-to-matching conversion.
The dog task	UVa	Easy	Bipartite Matching	Small Bipartite Graph; Matching	Matching Basics	Animals; Assignment	A compact warm-up that drills matching construction.

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Bipartite Matching	AOJ	Easy	-	-	-	Bipartite Graph; Augmenting Paths; Kuhn	Official bipartite matching baseline.
Guardian of Decency	UVa	Medium	Bipartite Matching, Independent Set	Compatibility Graph; Matching To Cover	Hall/Konig Intuition	Compatibility Graph	A classic compatibility graph that reduces to maximum matching.
School Dance	CSES	Medium	Bipartite Matching	Augmenting Paths; Bipartite Matching	Bipartite Graph Modeling	Bipartite Graphs; Pairing; Construction	Matching plus explicit pair recovery.
Stable Marriage	Canonical / Gale-Shapley	Medium	-	Two-Sided Preferences; Deferred Acceptance	Bipartite Pairing Model; Strict Preferences	Stable Matching; Preferences; Blocking Pair	The cleanest stability-based sibling once one-to-one pairing is no longer about size or cost.
General Matching	Library Checker	Hard	-	-	-	Blossom; Non-Bipartite; Verify	Trusted general-graph matching verification task.
Task Assignment	CSES	Hard	-	-	-	Assignment; Weighted Matching; Bipartite Graph	Weighted bipartite matching in assignment form.

Classics

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
A Plug for UNIX	UVa	Medium	Bipartite Matching, Adapter Graph	Reachability Closure; Max Matching	Graph Modeling	Conversion Graph	A very standard matching reduction with adapters and compatibility.
Antenna Placement	UVa	Medium	Minimum Vertex Cover	Grid Bipartization; Vertex Cover Extraction	Bipartite Graphs	Grid Graphs; Domination	Canonical grid-adjacency matching reduction.
Machine Schedule	UVa	Medium	Bipartite Matching, Job Assignment	Job-Machine Bipartite Graph; Minimum Cover Intuition	Minimum Vertex Cover Intuition	Scheduling	Another classic assignment problem with a matching core.

Advanced

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sorting Slides	UVa	Hard	Unique Assignment	Forced-Edge Reasoning; Matching Plus Uniqueness	Bipartite Matching; Geometry To Graph	Geometry; Deduction	A harder matching problem because uniqueness of assignment matters.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
QBFLOWER	Tặng hoa	primary	medium	minimum edge cover; general matching; graph transformation	Note	Code
SCHOOLDANCE	School Dance	primary	medium	-	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py