Almost-linear-time exact matching and prescribed-degree factors in general graphs. 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.
released 2026-09-24 | 2 theorems · 49 lemmas · 53 proofs · 43,901 words |
PLAY LEVEL 1 »(pdf)
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.