Almost-linear-time exact matching and prescribed-degree factors in general graphs

What OpenAI claims

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.

Paper

1. Almost-Linear-Time Maximum-Cardinality Matching in General Graphs

   24 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract 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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.