{"id":"openai-math/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs","pdf":"https://github.com/openai/math/blob/main/preprints/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026","tags":["graph-algorithms","matching","randomized-algorithms"],"score":0,"title":"Almost-Linear-Time Maximum-Cardinality Matching in General Graphs","domain":"Theoretical computer science","family":"120","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Almost-linear-time exact matching and prescribed-degree factors in general graphs"}