Browse › Theoretical computer science › 120 Almost-linear-time exact matching and prescribed-degree factors in general graphs

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

OpenAI · September 24, 2026

Open PDF Cite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

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.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Follow-up works

spele1100 (GitHub), reverse-matching: Reference implementation of 'Almost-Linear-Time Maximum-Cardinality Matching in General Graphs' (GitHub repository, 2026). A pure-Python reimplementation of the paper's reductions, phase machine, ledgers and assembly, tested against NetworkX blossom matching, with the pricing machinery of Sections 5–8 replaced by exact substitutes. The README states "Running time is not reproduced" and lists six deviations from the text. [AI-generated per source]

Possibly relevant literature (found by the agent, not checked)

Varsha Dani, Thomas P. Hayes, Seth Pettie, Maximum Matching on Regular Nonbipartite Graphs (arXiv:2609.14126, September 2026). Shows that blocking-flow algorithms run in deterministic $O(n^2)$ time on $d$-regular nonbipartite graphs. Relevant to the paper's comparison with Micali–Vazirani in the dense regime ($n^{2+o(1)}$ at $m=\Theta(n^2)$).
Dawei Huang, Seth Pettie, Approximate Generalized Matching: f-Factors and f-Edge Covers (arXiv:1706.05761, 2017, rev. 2020). Gives linear-time approximation schemes for weighted $f$-factors and exact cardinality versions in $O(m\sqrt{f(V)})$ time. These are prior bounds to compare with the paper's $f$-factor corollary, which the introduction compares only with Gabow's $O(n^{2/3}m)$.
Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi, Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation (arXiv:2511.08210, November 2025). A recent augmentation framework for general-graph maximum matching, positioned relative to Micali–Vazirani, in the combinatorial line that the paper's context section surveys.

Digests and expositions

Readable Intelligence, Almost-Linear-Time Maximum-Cardinality Matching in General Graphs (readable version) (readable-intelligence.com, undated). A rewritten readable version of the full paper; the page states that its proofs have not been independently checked. [AI-generated per source]
Gradient Damage, Unique Games Conjecture, Bin Packing and 8 More in Theoretical Computer Science (video compilation, 2026-10-15). Chapter 9, beginning at 2:49, illustrates the claimed almost-linear-time maximum-matching result, and the accompanying page reproduces the matching and prescribed-degree-factor guarantees. [family-level]

Elsewhere