Graphs -> Stable Marriage¶

Two-sided stable matching under complete strict preferences via Gale-Shapley deferred acceptance, with proposer-optimal output and blocking-pair avoidance.

Topic slug: graphs/stable-marriage
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 5
Curated external problems: 2

Microtopics¶

stable-matching
blocking-pair
deferred-acceptance
proposer-optimal
preference-ranks
two-sided-preferences

Learning Sources¶

Source	Type
AMS stable marriage and school choice	`Reference`
CACM stable marriage problem	`Reference`
Stable marriage interdisciplinary review	`Reference`

Practice Sources¶

Source	Type
Library Checker stable marriage problem	`Practice`

Repo Companion Material¶

Material	Type
Stable Marriage hot sheet	`quick reference`
Stable Marriage starter route	`starter route`
Stable Marriage note	`anchor note`
Matching tutorial	`compare point`
Hungarian tutorial	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Stable Marriage	`Canonical / Gale-Shapley`	`Medium`	Stable Matching, Gale-Shapley	Two-Sided Preferences; Canonical Benchmark	Bipartite Pairing Model; Strict Preferences	Blocking Pair; Deferred Acceptance	The cleanest in-repo flagship route where the whole job is just Gale-Shapley on complete strict preference lists.

Practice¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Stable Marriage Problem	`Library Checker`	`Medium`	Stable Matching, Gale-Shapley	Verifier-Style Problem; Stable Matching	Deferred Acceptance; Strict Preferences	Verify; Preferences	A natural verifier-style follow-up once the canonical Gale-Shapley route feels routine.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`STABLEMARRIAGE`	Stable Marriage	`primary`	`medium`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py