Exact general-graph matching in almost-linear time

Source and verification

This article explains family 120 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Matchings and exact witnesses

A matching in a graph is a set of edges with disjoint endpoints. Its maximum size is $\nu (G)$. A perfect matching covers every vertex; a maximum matching need not be perfect. An augmenting path alternates between edges outside and inside a current matching, with both endpoints unmatched. Toggling its edges increases the matching size by one.

The familiar bipartite flow construction does not immediately solve the general-graph problem. On a triangle, giving each edge weight $1/2$ satisfies every vertex constraint ${\sum }_{e\ni v}{x}_e\le 1$ and has fractional size $3/2$, but any matching has size one. Odd sets create the missing restrictions.

A graph on an odd number of vertices is factor-critical if deleting any one vertex leaves a perfect matching. A triangle is the smallest nontrivial example: any chosen vertex can remain exposed while the other two are matched. Such blocks allow an algorithm to move an exposed vertex without immediately rewriting every internal edge.

The manuscript combines this combinatorial representation with local flow repair and dynamic optimization. Its output is an explicit list of original edges, rather than only the value $\nu (G)$. (OpenAI, 2026)

🏷️ Input size and the runtime statement

The input is a simple, undirected, unweighted graph with $n\ge 1$ vertices and $m$ edges, stored in adjacency lists. Set $p=n+m$. Isolated vertices count toward $n$, lists may have any valid order, and connectedness is not assumed.

The machine is a randomized word-RAM with a fixed word length $\lceil c_0{\log }_2(n+2)\rceil$. Word arithmetic, memory operations, and each fair random bit have charged costs. Longer arithmetic is implemented using multiple words. Input processing, allocation, preprocessing, and output writing are included.

Manuscript statement

There is one uniform randomized algorithm, fixed constants $C,c_0$, and a nonnegative nonincreasing function $\eta (p)\to 0$ such that every computation path halts within

$$C{p}^{1+\eta (p)}$$

instructions. With probability at least $2/3$, it outputs a matching of size $\nu (G)$ as an explicit edge list. (OpenAI, 2026)

Here “exact” describes the optimum on the success event. It does not mean deterministic correctness. The time bound includes unsuccessful executions, so it is stronger than an expected-time bound. The construction verifies proposed matchings; its random errors can make a feasible threshold receive a negative answer, leading to a smaller returned matching.

If $m=O(n)$, this is $n^{1+o(1)}$. If $m=\Theta (n^2)$, it is $n^{2+o(1)}$, almost linear in the explicit dense input. No sublinear reading of an arbitrary adjacency-list input is claimed.

🏷️ Cardinality queries without quadratic expansion

Suppose one can find perfect matchings efficiently. To test whether $G$ has a matching of size $k$, a naive construction adds $b=n-2k$ new vertices adjacent to all original vertices. A perfect matching uses these new vertices to cover the unmatched originals. This can add $\Theta (n^2)$ edges, destroying a sparse input bound.

The source replaces those complete connections by a permutation-routing network with $O(n\log (n+2))$ positions and arcs. Every permutation can be routed through vertex-disjoint directed paths. Its recursive construction has two networks of half the size. A degree-two bipartite multigraph between input pairs and output pairs decomposes into even cycles; alternating their edges between the two smaller networks gives the routing induction.

Split each network position into an input and output vertex joined by an idle edge. A directed arc becomes an edge from one position’s output to the next position’s input. Connect each original vertex to its designated input, and attach $b$ mandatory sinks to selected outputs.

In a perfect matching, a split position is either idle or has both endpoints matched externally. Counting externally matched input and output endpoints cancels all transition edges. The mandatory sinks therefore force exactly $b$ original vertices to use network edges. The remaining $2k$ originals are matched by original graph edges, giving the decoded witness.

Conversely, a size-$k$ matching leaves $b$ originals uncovered. Route them to the selected sinks, extend their assignment to a permutation, and use idle edges at unused positions. This gives a perfect matching of the constructed graph. The total size is $O(m+n\log (n+2))$.

🏷️ Reducing degree while preserving the matching

After checking for isolated vertices, replace a vertex of degree $r$ by a path on $2r-1$ vertices. Attach its old incidences to the $r$ odd positions. The new graph has maximum degree three.

Every even path position must be matched internally to an odd one. There are $r-1$ even positions and $r$ odd positions, so exactly one odd position must use an external edge. Thus the gadget chooses exactly one original incidence. Conversely, after choosing that incidence, the two path segments on its sides have even lengths and can be matched internally.

For a graph with $v$ vertices and $e$ edges, the number of gadget vertices is

$$\sum _u(2\mathrm{deg}(u)-1)=4e-v.$$

The expansion is linear and retains original edge identifiers. These two reductions justify using a subcubic perfect-matching engine for maximum matching without losing either sparsity or explicit output.

🏷️ Odd blocks, allocations, and repair debt

The engine stores a partition into odd factor-critical blocks, outside singleton vertices, and matched pairs. The manuscript calls the odd blocks bins and certain outside singletons rows. A row may be assigned by an original edge to a distinct bin; inside the bin, all vertices except the endpoint of that edge are matched. An unassigned bin contributes one unmatched vertex. Repairs also track unmatched vertices set aside temporarily.

An allocation ledger distributes a fixed amount from each row among neighboring bins. A bin’s residual is its capacity minus its allocated load. Several ledgers require residual margins proportional to block size. A nonnegative debt records temporary violation of a margin.

The lowest ledger is debt-free at a settled state and certifies a strict Hall surplus for nonempty collections of bins. The highest ledger carries a logarithmic objective that must admit progress when a perfect matching exists and no structural operation applies. Intermediate margins make the resulting repairs affordable.

A local repair explores bins only when their debt is substantial relative to their size. An unexplored boundary bin initially accepts optimistic flow. If sufficient flow reaches it, exploration permanently locks in an absorbed amount proportional to the bin’s size. Since the total flow is bounded by the initial debt, these locks pay for the total number of vertices examined.

If the requested margin is infeasible, a cut identifies bins to remove. The gap between neighboring margins makes removal reduce debt in preserved coarser ledgers by an amount proportional to the removed size. Thus both exploration and structural deletion have a specific budget. Without that accounting, repeatedly opening large odd blocks could erase the almost-linear bound. (OpenAI, 2026)

🏷️ Exact feasibility from approximate optimization

Both the matching objective and repair tests use a priced circulation step: find a direction whose objective improvement is large relative to its weighted length, then take a small exact dyadic step. Conservation equations are maintained exactly throughout.

The source uses the discreteness of cut constraints to pass from sufficiently accurate numerical information to exact feasibility. If a nonzero obstruction must have integral size at least one, an error bound strictly below one cannot hide such an obstruction. This argument requires the relevant integral cut formulation and exact conservation; arbitrary small residuals in a floating-point relaxation would not suffice.

A dynamic forest representation stores long paths compactly. Two quantities must remain separate: signed coordinate changes and absolute motion. Traversing an edge once in each direction has zero net change but two units of absolute motion. Repricing and update costs depend on the latter, so cancellation cannot erase work already incurred.

The backend recursively routes and compresses circulations through frozen forest families. When representations change, stable copies retain their accumulated histories; replacing a copy first transfers that history. The manuscript supplies routing-load, traversal-length, and adaptive-update estimates for this interface. This article does not independently implement or verify that data structure.

🏷️ One program from many exponent bounds

For each sufficiently large fixed parameter $a$, the subcubic procedure has time

$$S^{1+O(1/a)+o_a(1)},$$

where $S$ bounds the reduced graph size. Having a different program for every exponent slack is not yet the stated uniform theorem. Nor may one silently assume a computable table telling the program when each asymptotic estimate becomes valid.

The source schedules branches indexed by $t$, using increasing fixed parameters, together with one exact polynomial-time fallback. In round $j$, branch $t\le j$ receives at most $2^{j-t}$ actual instructions. The total allowance through round $J$ is less than $2^{J+2}$. Any fixed branch needing $T$ instructions therefore competes within a factor of order $2^t$, apart from charged control and input costs.

Large arithmetic, initialization, and allocation are interruptible sequences of instructions, not atomic operations. The fallback bounds total physical storage and guarantees halting on every random path. Deterministic prerequisite failures suspend a branch; exhausted random retries instead give a possibly false negative test result.

Each branch performs threshold search and verifies accepted witnesses. Let $E$ be the event that the final answer is incorrect. Summable error allowances give

$$\mathrm{Pr}(E)\le \sum _{t\ge 1}{2}^{-(t+20)}<\frac{1}{3}.$$

This is a union bound over complete branch streams, without conditioning on which branch finishes first. For every fixed exponent slack, the analysis chooses one sufficiently advanced branch. The running program itself makes no such input-dependent choice. A tail supremum of its actual time exponents then gives the common nonincreasing envelope $\eta (p)\to 0$.

The manuscript also obtains prescribed-degree factors: given integers $0\le f(v)\le \mathrm{deg}(v)$, find a spanning subgraph with degree exactly $f(v)$ at every vertex, or decide that none exists. Its witness-preserving reduction has logarithmic expansion in edge incidences. This is another exact combinatorial output, not the approximate counting problem for perfect matchings.

🏷️ Key steps and proof outlines

The permutation network preserves sparse input size

The “Witness-preserving reductions” section recursively constructs a network on $s$ inputs and outputs, with $s$ a power of two. Pair inputs and outputs and place two disjoint networks of size $s/2$ between them. For a desired permutation, create a bipartite multigraph between input pairs and output pairs, with one edge for each requested route. Every vertex has degree two, so each component is an even cycle. Alternating cycle edges between the upper and lower subnetworks gives one route per pair in each half. Induction routes them without collisions. (OpenAI, 2026)

The size recurrence $Q(s)=2Q(s/2)+O(s)$ gives $O(s\log s)$ positions and arcs. This is the feature that prevents the cardinality reduction from adding a dense complete bipartite graph.

After splitting each network position into input and output endpoints, every perfect matching uses either its idle edge or two external incidences. Count externally matched endpoints of each kind. Transition edges contribute equally to both counts and cancel. The $b=n-2k$ mandatory sinks leave a difference of exactly $b$, so exactly $b$ original vertices attach to the network. The remaining originals contribute an explicit matching of size $k$. The reverse construction routes the uncovered originals to the sinks and uses idle edges elsewhere. Thus both directions preserve witnesses, including the case $b=0$.

Path gadgets reduce degree with an exact parity count

Replace a degree-$r$ vertex by a path with $2r-1$ vertices and attach old edges at odd positions. All $r-1$ even positions must be matched internally. They consume $r-1$ distinct odd positions, leaving exactly one for an external edge. Conversely, after selecting one odd attachment, the two remaining path segments have even lengths and admit their consecutive-edge perfect matchings.

The total gadget vertex count is ${\sum }_v(2\mathrm{deg}(v)-1)=4m-n$ when there are no isolates. Old edge identifiers are retained, so decoding consists of selecting the external old edges. Isolated vertices are handled before this construction. These elementary reductions explain the exact output interface consumed by the much more involved subcubic solver.

Local flow repair needs a size charge, not merely termination

Inside the subcubic solver, debt measures violations of residual margins in allocation ledgers. A boundary bin is initially treated optimistically. When repair sends enough flow toward it to require exploration, a fixed amount proportional to its size is permanently charged to the incoming flow budget. Summing these charges bounds total explored volume by initial debt. If a flow cut proves the desired margin infeasible, removing its bins decreases debt at a coarser margin by a comparable size charge.

The margin hierarchy is therefore an amortization device: every expensive opening or deletion must spend a resource whose total is controlled. Factor-critical blocks store the matching information needed to reroute exposed vertices, while the circulation backend must charge absolute edge motion as well as net flow. These interfaces are what allow the source’s dynamic optimization to translate into a bound on actual graph operations.

Uniformization preserves both time and probability

For branch $t$, assign an increasing fixed solver parameter and error allowance proportional to $2^{-t}$. In scheduling round $j$, allocate at most $2^{j-t}$ instructions to branch $t\le j$. Summing over branches and rounds up to $J$ is $O(2^J)$. Hence any fixed branch completing in $T$ instructions is simulated with only a fixed branch-dependent multiplicative overhead.

Each accepted perfect-matching witness is checked exactly, so threshold search has no false positive feasibility answer. A union bound over all reached tests in all branch streams controls false negatives without conditioning on the identity of the first finishing branch. That conditioning could bias error probabilities. An exact fallback guarantees completion, while every fixed exponent slack is eventually witnessed by some sufficiently advanced branch. This produces one program with almost-linear asymptotic work, rather than an unspecified family of programs selected using unknown thresholds.

See Also

• Counting perfect matchings concerns the number and entropy of solutions; constructing one optimum matching has different guarantees.
• Integer multiplication explains why arithmetic precision and physical data movement must be included in a computational bound.
• Edit-distance approximation provides a useful comparison: its almost-linear bound is expected time, for each fixed accuracy.

🏷️ Manuscripts and verification scope

• Almost-Linear-Time Maximum-Cardinality Matching in General Graphs — pinned manuscript and companion source.

No family scope page was present at lean/docs/120.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Almost-Linear-Time Maximum-Cardinality Matching in General Graphs.