Gives a randomized algorithm finding an exact maximum-cardinality matching in any simple undirected graph in (n+m)^{1+o(1)} word time, with success probability at least 2/3. The time bound holds on every computation path. The same guarantees apply to finding a spanning subgraph with prescribed admissible vertex degrees, or deciding that none exists.
Manuscript
Almost-Linear-Time Maximum-Cardinality Matching in General Graphs
September 24, 2026 · source · cite as \cite{OAI:Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026}
We prove that maximum-cardinality matching in a simple undirected graph with n vertices and m edges can be found by one uniform randomized algorithm in (n+m)^{1+o(1)} time. The bound holds on every computation path in a logarithmic-word model, and the algorithm returns an explicit maximum matching with probability at least 2/3. An explicit reduction gives the same time and probability guarantees for deciding whether a simple host graph has a spanning subgraph with prescribed valid vertex degrees, and for finding one when it exists.
Result 120 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Agora members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md