1 · The essentials
Imagine a network of points joined by links, where you want to choose as many links as possible without choosing two that touch the same point. The manuscript presents a randomized method for finding an exactly largest such selection, not merely a nearly largest one. It applies to undirected networks with no links from a point to itself and no repeated links between the same two points. Its stated running time is almost linear in the combined number of points and links. The time limit holds for every possible sequence of random choices, while the chance of returning a correct largest selection is at least two-thirds. The manuscript also gives the same guarantees for choosing links so that every point has a specified number of chosen links, or deciding that this is impossible. These results are shown in the manuscript, but the main result is not formalized in Lean and has not been formally verified.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine people who can pair up only when a link in a contact list allows it: the goal is to form as many disjoint pairs as possible. The second task instead asks for a set of allowed contacts in which each person has exactly their requested number of contacts. This picture captures the selection rules, but not how the algorithm works or why its running time is small.
Why it matters
The result combines an exact optimization goal with an almost-linear running-time guarantee for general simple undirected graphs. It separates two guarantees that should not be confused: the time bound holds on every computation path, but correctness is guaranteed with probability at least two-thirds. The reduction extends those guarantees to the related task of meeting prescribed vertex degrees.
2 · Going further
For a simple undirected graph with vertices and edges, a matching is a set of edges no two of which share a vertex. The maximum-cardinality matching problem asks for a matching containing as many edges as possible. The manuscript states that one uniform randomized algorithm returns an explicit maximum matching with probability at least in time, measured in a logarithmic-word model. The time bound applies on every computation path, rather than only on average over the random choices.
The related prescribed-degree problem starts with a simple host graph and valid requested vertex degrees. It asks for a spanning subgraph—one retaining every vertex and selecting some of the host graph's edges—in which each vertex has its requested degree. The abstract states that an explicit reduction gives the same running-time and success-probability guarantees both for deciding whether such a subgraph exists and for finding one when it does.
The supplied abstract does not describe the internal matching algorithm or the details of its argument. The explicit reduction is the only argument-level connection it identifies between the two tasks. Only the main manuscript is supplied, so no relationship to companion manuscripts or comparison with earlier running-time bounds can be established from this source.
Useful notions
- Vertices and edges of a graph
- Matchings and maximum cardinality
- Vertex degrees and spanning subgraphs
- Randomized algorithms and success probability
- Asymptotic running time and word-based computation
What was known before / what is new
Before
The source identifies maximum-cardinality matching and the prescribed-degree spanning-subgraph task as the problems under study. It does not state earlier algorithms, previous running-time bounds, or historical milestones, so it does not support a more specific account of what was known before.
New
The manuscript presents one uniform randomized algorithm for exact maximum-cardinality matching in any simple undirected graph, with running time on every computation path and success probability at least . It also presents an explicit reduction giving the same guarantees for deciding and constructing prescribed-degree spanning subgraphs.
Limits and assumptions
The stated scope is simple undirected graphs, with valid prescribed vertex degrees for the spanning-subgraph task. The time guarantee is in a logarithmic-word model and holds on every computation path; the correctness guarantee is probabilistic, not certain. The supplied abstract does not detail the algorithm, the reduction, or the conditions meant by valid degree prescriptions, and it identifies no remaining open problems. The main result is not formalized in Lean and has not been formally verified.
Mini glossary
- Simple undirected graph —
- A network whose edges have no direction, with no edge joining a vertex to itself and no repeated edge between the same two vertices.
- Maximum-cardinality matching —
- A largest possible set of edges in which no two edges share a vertex.
- Vertex degree —
- The number of edges touching a vertex.
- Prescribed-degree factor —
- A spanning subgraph in which each vertex has its specified degree.
- Almost-linear time —
- Here, a running-time bound of , whose exponent approaches one as the input size grows.
- Computation path —
- A particular course of execution of the randomized algorithm, including the random choices it makes.
Keywords : Maximum-cardinality matching · Almost-linear time · Prescribed-degree factors
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Gives a randomized algorithm finding an exact maximum-cardinality matching in any simple undirected graph in 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.
To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.
Manuscripts in this family
Almost-Linear-Time Maximum-Cardinality Matching in General Graphs
24/09/2026We 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 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.