Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 120: almost-linear-time exact graph matching

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This documentary article describes a claim in the pinned publisher overview, not an independently verified algorithm.

The question in plain language

A matching in a graph is a collection of edges with no shared endpoints. A maximum-cardinality matching contains as many edges as possible. Unlike simply finding a large matching, computing an exact maximum must rule out every possible improvement.

Family 120 reports a randomized algorithm purportedly computing an exact maximum matching in almost linear time even for general, nonbipartite graphs. The reported method also handles prescribed-degree spanning subgraphs.

A small example

Suppose a graph is a path of four vertices. Its two outer edges form a matching of size two, which is maximum. A greedy method might first choose the middle edge and produce only one matched pair. In general graphs, odd cycles make exact matching harder to analyze than in bipartite graphs.

A prescribed-degree factor asks for a spanning subgraph in which each vertex has an assigned number of incident selected edges. Ordinary matching corresponds to degree at most one, whereas factor problems can demand a range of higher degrees. These outputs must not be confused.

What is known

The protected Family 120 catalogue identifies one manuscript, Almost-Linear-Time Maximum-Cardinality Matching in General Graphs.

The pinned publisher overview claims that every simple undirected graph with \(n\) vertices and \(m\) edges admits a randomized algorithm producing an exact maximum-cardinality matching in

\[ (n+m)^{1+o(1)} \]

word operations, with success probability at least \(2/3\). It explicitly says that this running-time bound holds on every computation path, rather than merely in expectation.

The overview additionally claims the same asymptotic time and success guarantees for producing a spanning subgraph with prescribed admissible vertex degrees, or deciding that none exists. The word “admissible” needs its exact definition from the primary paper, especially when a degree prescription is infeasible.

This is a randomized exact-output algorithm, not a deterministic algorithm or a randomized approximation scheme. Its word-operation bound is not automatically a bit-complexity guarantee without an explicit machine-word model.

GCL verification state

Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The protected catalogue supplies the PDF path and the pinned publisher overview supplies the exactness, graph class, success probability, running-time model, and prescribed-degree extension.

The proof, reduction, data structures and complexity analysis have not been independently checked in this documentary pass. No Family 120-specific source-critical proof audit, Lean trust-chain attestation, Comparator result, or MATHCERT certificate is asserted.

What remains

Read the pinned PDF and extract the complete theorem statements, including the word-RAM model, input encoding, the meaning and uniformity of the \(o(1)\) exponent, and whether preprocessing or random-bit generation is included. Verify that the algorithm returns a maximum matching, not just a matching whose size is close to optimal, and that its success probability applies uniformly to all inputs.

Check the proof of the bound on every random computation path, including any capped retries or fallback computations. For prescribed-degree factors, determine the precise input admissibility assumptions, whether degrees must be feasible or are validated by the algorithm, and whether the output is an exact certificate of feasibility or infeasibility.

Run documentary validation and MkDocs rendering checks, complete source criticism, and merge through protected governance with exact-head readback. Documentary admission alone does not certify the mathematical claims.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. The claimed exact randomized algorithms remain subject to independent verification.


Indexed primary manuscript paths: