edmonds-blossom-maximum-matching
The inline self-check matches the document exactly. Solution complete.
I built, tested, and documented a correct Edmonds' blossom implementation in ~/:
blossom.py — the deliverable module: max_matching(adj), verify_matching(adj, match), matching_cardinality, tutte_berge_witness, plus brute-force/naive references for testing.test_blossom.py — full test harness.SOLUTION.md — the write-up (title, root-cause analysis, exact code, verification).A blossom-free alternating-path search never contracts odd cycles. An alternating tree then stops being a tree (same-parity edge), and augmenting paths that enter and leave a blossom become invisible — so the search quiesces at a maximal but non-maximum matching.
Standard O(V^3) blossom algorithm using base[] to represent contraction (no graph mutation, so the matching is always on original vertices): correct lca via base-lifting, mark_path on both arms, re-enqueueing every vertex whose base becomes the blossom, and a safe augmenting-path flip.
n ≤ 6 exhaustive + seeded random n = 7..10 — exact parity with exponential brute force, every matching validated.C5=2 C7=3 C9=4 Petersen=5 K4=2 K5=2 K6=3 K7=3.n=2000 sparse in 0.14 s; n=2000 dense (99,849 edges) in 0.22 s; n=1000 p=0.3 in 0.55 s.C5/C7, U=∅, one odd component, deficiency 1, nu=(n−1)/2; Petersen is perfect. optimal=True confirms maximum (not just maximal).# Evidence - Problem class: edmonds-blossom-maximum-matching - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-17T22:04:00.926Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement Edmonds' blossom algorithm for maximum-cardinality matching in a general (non-bipartite) graph from scratch, including blossom contraction/detection, the alternating-tree augmentation step, and expansion back into the original vertex set. The deliverable is a single module exposing max_matching(adj) plus a verify_matching() that proves the returned edge set is a valid matching, and it must return maximum cardinality on graphs containing odd cycles (C5, C7, Petersen, complete graphs K2n/K2n+1) where the naive Hungarian augmenting-path approach fails. Acceptance: exact cardinality parity with a brute-force exponential reference on all graphs with n<=10 (exhaustive or seeded random), linear-time-scale results on random sparse/dense graphs with n up to 2000, and a certificate of optimality via a Gallai-Edmonds/Tutte-Berge odd-set witness for at least one non-perfect case.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "edmonds-blossom-maximum-matching", "provider": "openrouter", "solved_at": "2026-09-17T22:04:00.926Z", "version": "3.11"}The inline self-check matches the document exactly. Solution complete.
I built, tested, and documented a correct Edmonds' blossom implementation in ~/:
blossom.py — the deliverable module: max_matching(adj), verify_matching(adj, match), matching_cardinality, tutte_berge_witness, plus brute-force/naive references for testing.test_blossom.py — full test harness.SOLUTION.md — the write-up (title, root-cause analysis, exact code, verification).A blossom-free alternating-path search never contracts odd cycles. An alternating tree then stops being a tree (same-parity edge), and augmenting paths that enter and leave a blossom become invisible — so the search quiesces at a maximal but non-maximum matching.
Standard O(V^3) blossom algorithm using base[] to represent contraction (no graph mutation, so the matching is always on original vertices): correct lca via base-lifting, mark_path on both arms, re-enqueueing every vertex whose base becomes the blossom, and a safe augmenting-path flip.
n ≤ 6 exhaustive + seeded random n = 7..10 — exact parity with exponential brute force, every matching validated.C5=2 C7=3 C9=4 Petersen=5 K4=2 K5=2 K6=3 K7=3.n=2000 sparse in 0.14 s; n=2000 dense (99,849 edges) in 0.22 s; n=1000 p=0.3 in 0.55 s.C5/C7, U=∅, one odd component, deficiency 1, nu=(n−1)/2; Petersen is perfect. optimal=True confirms maximum (not just maximal).# Evidence - Problem class: edmonds-blossom-maximum-matching - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-17T22:04:00.926Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement Edmonds' blossom algorithm for maximum-cardinality matching in a general (non-bipartite) graph from scratch, including blossom contraction/detection, the alternating-tree augmentation step, and expansion back into the original vertex set. The deliverable is a single module exposing max_matching(adj) plus a verify_matching() that proves the returned edge set is a valid matching, and it must return maximum cardinality on graphs containing odd cycles (C5, C7, Petersen, complete graphs K2n/K2n+1) where the naive Hungarian augmenting-path approach fails. Acceptance: exact cardinality parity with a brute-force exponential reference on all graphs with n<=10 (exhaustive or seeded random), linear-time-scale results on random sparse/dense graphs with n up to 2000, and a certificate of optimality via a Gallai-Edmonds/Tutte-Berge odd-set witness for at least one non-perfect case.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "edmonds-blossom-maximum-matching", "provider": "openrouter", "solved_at": "2026-09-17T22:04:00.926Z", "version": "3.11"}