Maximum-cardinality matching in general graphs in almost-linear time
Given a simple undirected graph with vertices and edges, find a maximum-cardinality matching. Edmonds' blossom algorithm gave polynomial time; Micali and Vazirani (1980) achieved , which remained the best combinatorial bound for sparse general graphs, while algebraic methods give . After almost-linear-time exact max flow (Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva, 2022) gave almost-linear bipartite matching, the general-graph case, where odd cycles (blossoms) defeat the flow formulation, remained open. Can a maximum matching in a general graph be found in time?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Graph algorithms; matching
- Posed by
- Long-standing open algorithmic question (no single poser cited in the manuscript); benchmark bound Micali and Vazirani (1980), bipartite case settled by Chen et al. (2022)
- Year posed
- —
- Years open
- —
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 48 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: a single uniform randomized algorithm finds a maximum-cardinality matching of any simple graph in word operations on every path, with success probability at least and explicit output. Corollary: the same guarantees for deciding and constructing -factors (prescribed-degree spanning subgraphs). It is randomized (no deterministic version), unweighted (maximum-weight general matching is not addressed), and the is not made explicit.
What the AI did
Produced by an unreleased internal OpenAI model as part of the openai/math release (pinned commit adc7f12). The release README says results were produced by one fixed procedure averaging about three hours of ChatGPT Pro thinking compute each; this result is not among the README exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored as OpenAI with no human author named. No Lean formalization accompanies it.
Verification
No independent mathematician has checked this yet. Checked here: abstract, introduction and Theorem 1.1 of the TeX source, read against the general-graph matching question. Theorem 1.1 states one uniform randomized word-RAM algorithm that halts within instructions on every computation path (, ) and outputs an explicit maximum matching with probability at least . It is Monte Carlo: correctness of the output is not certified. The algorithm uses the deterministic almost-linear flow theorem (van den Brand et al.) as a black box. Not refereed here. No Lean formalization.