Almost-linear-time exact matching in general graphs

← All digests

Family 120 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

A matching pairs vertices without using any vertex twice. Finding a largest matching has been a cornerstone of graph algorithms since the development of blossom methods. Family 120 claims that an exact maximum matching in a general graph can be found in time almost proportional to the input size, with constant success probability and an execution-time bound that includes unsuccessful random runs.

1. The question

Suppose edges record compatible pairs of objects. We want to choose as many disjoint pairs as possible. Greedily choosing an available edge can get stuck too early: on a path with four vertices, choosing its middle edge gives only one pair, whereas choosing the two outside edges gives two.

A matching to which no edge can simply be added is maximal. A matching with the largest possible number of edges is maximum. The theorem concerns the latter, more demanding objective.

General graphs contain odd cycles, unlike bipartite graphs, whose vertices split into two parts with every edge crossing between them. Odd cycles complicate the exchanges used to enlarge a matching.

The manuscript claims an algorithm taking $(n+m)^{1+o(1)}$ word operations for $n$ vertices and $m$ edges. It must return the actual matching edges, not just the optimum’s numerical size.

2. Background and essential definitions

Alternating paths and blossoms

Relative to a current matching, an alternating path uses unmatched and matched edges in turn. If it begins and ends at unmatched vertices, switching the chosen status of its edges increases the matching size by one. Such a path is augmenting.

In bipartite graphs, searching for augmenting paths has a relatively direct layered structure. In general graphs, an alternating search can encounter an odd cycle. Blossom algorithms contract suitable odd structures, continue the search in a smaller representation, and later expand them to recover a valid matching.

A related notion is a factor-critical set: after deleting any prescribed vertex from that set, its remaining vertices have a perfect matching. It can therefore expose different vertices to connect with the rest of the graph while pairing all its other vertices internally.

Input size and almost-linear time

The input graph is simple, undirected, and unweighted. Its adjacency lists contain two neighbor occurrences per edge, together with boundaries for the vertex lists. Isolated vertices count toward the input size.

Put $p=n+m$. Almost-linear time means a bound

$$C p^{1+\eta(p)},\qquad \eta(p)\longrightarrow0.$$

This is close to linear at the exponent level. It does not necessarily mean $O(p\log^c p)$ for a fixed $c$, which is a stronger and more specific kind of bound.

The computational model is a word-RAM with words of $O(\log(n+2))$ bits. Basic operations on such words have unit cost. Longer arithmetic, random-bit generation, data movement, initialization, and writing the output are charged.

Prescribed-degree subgraphs

An $f$-factor is a spanning subgraph in which each vertex $v$ has a prescribed degree $f(v)$. “Spanning” means it keeps every vertex, though some may have prescribed degree zero.

Perfect matching is the case $f(v)=1$ everywhere. More general prescriptions ask for several incident edges at some vertices, subject to the edges actually available in the host graph.

3. Development history and previous partial results

Hall’s theorem characterizes complete pairing on one side of a bipartite graph. Tutte’s theorem identifies the additional odd-component obstruction in general graphs. These existence results reveal the structures algorithms must manage.

Edmonds’s blossom algorithm made general-graph matching polynomial-time. His matching-polytope description also explains why vertex-degree constraints alone are insufficient: assigning one half to every edge of a triangle satisfies those constraints but has total fractional size one and a half, whereas an integral matching has size at most one.

Hopcroft and Karp accelerated bipartite matching by finding many shortest augmenting paths in phases. The Micali–Vazirani algorithm extended the square-root-times-edges scale to general graphs, conventionally $O(m\sqrt n)$, with input-reading costs included when needed.

Algebraic methods provide a different route. Randomized evaluations of the Tutte matrix connect matching with linear algebra. Mucha and Sankowski and Harvey developed algorithms producing explicit maximum matchings at the matrix-multiplication time scale. Such bounds are especially relevant for dense graphs.

For bipartite graphs, exact matching reduces to integral flow. Almost-linear flow algorithms, including the deterministic minimum-cost flow result of van den Brand and collaborators, consequently yield almost-linear bipartite matching.

The remaining challenge addressed here is the general graph: retain the efficiency of modern flow and continuous-optimization machinery while handling odd blocks and recovering explicit edges. M1 incorporates that structure rather than assuming a bipartite reduction with no overhead or loss.

4. What the new manuscripts claim

M1 states that one uniform randomized word-RAM algorithm halts on every computation path within

$$C(n+m)^{1+\eta(n+m)}$$

instructions, for a nonincreasing function $\eta$ tending to zero. With probability at least $2/3$, it outputs a list of edges forming a maximum-cardinality matching.

A perfect matching is not promised. The graph may be disconnected and contain isolated vertices, and adjacency lists may appear in any valid order.

On graphs with $m=O(n)$, the bound is $n^{1+o(1)}$. At the dense extreme $m=\Theta(n^2)$, it is $n^{2+o(1)}$. The same finite algorithm and exponent envelope cover the whole density range.

The paper also claims the same almost-linear time and success probability for deciding whether an $f$-factor exists and returning it when it does. The supplied degrees satisfy $0\le f(v)\le\deg_G(v)$ and fit in ordinary machine words.

“Exact” refers to the optimum attained on successful runs. The algorithm is randomized and may fail with the stated probability; exact optimization is not synonymous with deterministic certainty.

5. Why the advance matters

Importance: 4/5, provisional. Maximum matching is a fundamental polynomial-time optimization problem. An almost-linear algorithm across all graph densities would substantially narrow the asymptotic distance between reading the input and solving it exactly.

The sparse case is particularly significant. A bound expressed only through matrix multiplication may spend far more than linear time even when the graph has few edges. The claimed input-size guarantee responds to actual sparsity.

The $f$-factor consequence broadens the result to prescribed-degree design problems. Its reduction must preserve a compact instance and recover a concrete subgraph, so it is more informative than an abstract equivalence of decision problems.

The claim is an asymptotic complexity advance, not a benchmark for a usable matching library. It also concerns cardinality; arbitrary maximum-weight matching is a separate objective.

6. The main idea

Reduce to a manageable exact subproblem

The paper’s central procedure finds perfect matchings in graphs of maximum degree three. Reductions convert general cardinality questions to this task while retaining identifiers that allow returned edges to be decoded into the original graph.

Bounding degree limits local complexity. The reductions must also limit total size; replacing a vertex by a huge gadget would erase the intended running-time improvement.

Store odd blocks without repeatedly opening them

The matching state groups some vertices into odd factor-critical blocks. Each block carries information about an internal matching with any designated vertex exposed. Outside vertices can be assigned to blocks through original edges.

This allows the algorithm to change how a block connects externally without rebuilding its entire internal matching immediately. It extends the basic contraction-and-expansion idea with a representation designed for frequent local updates.

The difficulty is that structural changes can invalidate assignments. Repairing every affected structure by scanning all its vertices would be too expensive.

Let accumulated imbalance pay for repairs

The construction maintains several allocation records at different margins. A record distributes available contributions among neighboring blocks; its residual describes remaining capacity. A nonnegative debt allows a temporary failure of the desired margin.

When a repair starts, it explores only blocks with enough debt relative to their size. Exact flow computations either repair the allocation or identify a collection of blocks to remove from that state. The bookkeeping ensures that useful progress or a decrease in debt pays for the amount of structure examined.

This is an amortized analysis: one operation may be costly, but repeated costly operations require a resource that cannot be spent indefinitely. The paper makes the resource explicit across several scales of constraints.

Search for improvement in compressed representations

The optimization procedure seeks circulation directions that give sufficient progress relative to weighted length. A circulation is an assignment of directed edge flows with no net accumulation at vertices.

Dynamic forests and routing summaries represent long paths compactly. The algorithm tracks both signed coordinate changes and total absolute motion, because opposite movements may cancel algebraically while still costing computation.

A hierarchy of routing structures preserves these quantities as representations change. Finally, schedules over fixed-parameter procedures produce one uniform algorithm with a common exponent tending to one. This last step matters: a separate algorithm for each desired exponent slack would be a different assertion.

7. Scope, limitations, and open questions

The headline theorem assumes a simple unweighted graph explicitly stored by adjacency lists. It does not assert the same bound for compressed graph descriptions, arbitrary edge weights, or every model of accessing a graph.

Its time bound holds on every random path, while its correctness guarantee is probabilistic. The stated $2/3$ success probability should not be silently replaced by certainty or by a stronger high-probability claim.

The $o(1)$ exponent does not specify a small practical overhead. Constants, thresholds, and the cost of sophisticated dynamic structures remain relevant to implementation.

The natural further directions include deterministic general-graph matching at comparable complexity, simpler explicit overheads, and corresponding results for weighted objectives. They are separate from the family theorem.

8. Sources and further reading

M1’s Theorem 1.1 fixes the input representation, machine operations, success probability, and uniformity. Its final section states the prescribed-degree consequence. The classical matching and modern flow papers linked above explain the combination of odd-set structure and efficient continuous optimization that motivates the construction.

Source manuscripts

• M1. OpenAI, Almost-Linear-Time Maximum-Cardinality Matching in General Graphs (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.