Almost-linear-time maximum matching in general graphs
Almost-linear-time maximum matching in general graphs concerns the time needed to find a maximum-cardinality matching in a graph that need not be bipartite. As the manuscript recounts, the classical bound for general graphs is the O(m√n) of Micali and Vazirani, while almost-linear exact algorithms were known only for bipartite graphs, through maximum flow. A manuscript in OpenAI's public mathematics collection (github.com/openai/math), dated 24 September 2026, claims a randomized algorithm running in almost-linear time in the input size for every general graph, and the same bound for finding prescribed-degree factors. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper or code is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Berge's augmenting-path criterion was made algorithmic for general graphs by Edmonds' blossom algorithm. Micali and Vazirani gave running time O(m√n); Gabow and Tarjan reached the same bound by weighted scaling, and Goldberg and Karzanov improved it slightly on very dense graphs. Mucha and Sankowski, and then Harvey, obtained randomized algorithms at the matrix-multiplication time scale.
- For bipartite graphs, Mądry's electrical-flow interior-point method and the work of van den Brand et al. were intermediate steps, and the almost-linear exact flow algorithms of Chen et al. and of van den Brand et al. give almost-linear bipartite matching. The manuscript states that general graphs require additional control of odd sets, and that its routing hierarchy builds on the dynamic minimum-ratio-cycle framework of those flow papers.
The original result
- Claim. Theorem 1.1 of Almost-linear-time maximum-cardinality matching in general graphs states that one uniform randomized word-RAM algorithm halts on every computation path within C · p1 + η(p) instructions, where p = n + m and η tends to zero, and with probability at least 2/3 outputs an explicit maximum matching of a simple undirected graph with n vertices and m edges. A corollary gives the same guarantees for deciding whether a graph has a spanning subgraph with prescribed vertex degrees and for finding one.
- Source. The manuscript Almost-linear-time maximum-cardinality matching in general graphs at commit
1581d4c. - Formalization. The collection lists no Lean formalization for this result.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 20 October 2026) |
|---|---|---|---|---|
| 2026-10-10 | spele1100/reverse-matching (GitHub, commit fe24f72) |
Use (implementation) | A correctness-only reference implementation in Python of the manuscript's matching machinery, which the README describes as an AI-assisted paper reproduction checked against an oracle in more than 250 tests. The README states that the manuscript's asymptotic running-time claims are not reproduced. | GitHub repository. |
| 2026-10-11 | spele1100/dynamic-matching (GitHub, commit c2a31ff) |
Related software | A library maintaining an exact maximum matching of a general graph under edge insertions and deletions, with one blossom search per update. The README states that it grew out of the reference implementation above, while its core search is a classical blossom search extended to a multi-root forest. | GitHub repository. |
| 2026-10-16 | J. Jardine, Lattice24, referee review rank_237 in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap, with no minor note. The reviewer states that it read Sections 1–5, 9 and 10 in detail, together with the main lemma and recursion proofs of Section 7 and the sampling lemma of Section 6, and only skimmed the rest of Sections 6–8, namely the routing-helper overlay and router and the backend update and forest-lifting machinery. | Part of an audit of the collection's manuscripts without Lean that the audit describes as complete. The reviews are published under CC BY 4.0. |
Notes
- The earlier matching and flow algorithms are due to the authors named in the Background section, as recounted by the manuscript.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.