Almost-linear-time exact matching and prescribed-degree factors in general graphs

The explanation

Take five people sitting in a ring, each friends with the two beside them. You want to pair friends off, with no one in two pairs. A set of such pairs is a matching [a set of links with no shared endpoint]Source 1. The best you can do here is two pairs. With five people, one is always left out.

Odd rings like this are the classic trap. Try a triangle and give each of its three links a weight of ½. Every person then has total weight 1, so the per-person limits are metSource 2. The weights add up to 1.5, yet a real matching in a triangle has just one pair. Rules about single people miss the odd-set problem.

For graphs without odd rings, called bipartite, matching is a kind of network flow. Recent flow algorithms run in almost-linear time [time close to the size of the input]. That gives almost-linear exact bipartite matchingSource 3. General graphs require extra control of odd blocksSource 4. Edmonds handled odd blocks in 1965 by shrinking them into single points, called blossomsSource 5. The Micali–Vazirani algorithm runs in time of order m√n, with n vertices and m linksSource 6.

Put numbers on that. Take a network with a million vertices and three million links. The input has about four million items. The m√n bound is 3,000,000 × 1,000, or three billion steps. Algebraic methods run at matrix-multiplication speed instead, which helps most on dense graphsSource 7.

This paper claims one randomized algorithm that finds a largest matching in (n + m) raised to the power 1 + o(1) stepsSource 8. The o(1) is an extra exponent that shrinks toward zero as graphs grow. The paper gives no numerical value for it. The time bound holds on every run, even unlucky onesSource 9. With probability at least 2/3, the output is an explicit list of matched linksSource 10.

The same guarantees cover a wider taskSource 11. Each vertex gets a target number of links, between zero and its full count. The algorithm decides whether some set of links hits every target exactly, and finds one if so.

The hard part sits in a core subproblem: a perfect matching in a graph where every vertex has at most three linksSource 12. The algorithm keeps a current matching organized around odd blocks. When the structure changes, it must repair this record without rescanning every odd blockSource 13. The paper does this with layered accounts that allow small temporary debts, then pays them back with bounded work. It also builds on the almost-linear flow framework for its search directionsSource 14.

How sure is this? No Lean formalization is listed for this paper in the openai/math release. So no computer proof checker has checked it. No specialist review has been published.

What it doesn't show. This does not handle weighted matching, and it does not give a deterministic algorithm.