PaperfootJoin free
arXiv

Algorithm finds largest graph pairings in near-quadratic time

For general graphs, the algorithm’s running-time bound grew nearly as the square of the number of points when finding the largest set of non-overlapping links.

Paper by George Z. Li, Jason Li, Junkai Zhang
A light blue network contains distinct black pairs, surrounded by scattered dark blue-green circles, gray strips, and a smaller branching network.
Preprint: method

Edited by Boris Djordjevic · Paperfoot

Paper

The preprint presented an algorithm for maximum-cardinality matching in general graphs: finding the largest possible set of links with no shared endpoints. A graph consists of points and links between them. The algorithm had a nearly quadratic running-time bound, with an exponent approaching two as the number of points grew.

The method built on recent combinatorial algorithms for maximum flow, the problem of routing as much flow as possible through a network subject to capacity limits. It extended those techniques to another class of flow problems that includes general graph matching as a special case.

Why it matters

The result gave a guarantee about how computation grows with graph size. It also extended techniques from maximum-flow algorithms to problems that capture general graph matching.

Caveats

The abstract reports a theoretical running-time bound, not measured speeds or comparisons with earlier algorithms. The paper is an arXiv preprint, not yet peer-reviewed.

In this paper

maximum cardinality matching

Methods
regular reachability algorithm

What it shows

A regular path from s to s' exists if and only if no barrier from s to s' exists.

A regular path from s to s^{\prime} exists if and only if no barrier from s to s^{\prime} exists.

Theorem 9.

An integral symmetric flow on a unit-capacity skew-symmetric graph is maximum if and only if its residual graph has no regular path from s to s'.

The flow f is maximum if and only if there is no regular path from s to s^{\prime} in this residual graph.

Theorem 10.

Augmenting one unit along a regular path from s to s' and its symmetric path yields an integral symmetric flow of larger value.

If there is a regular path from s to s^{\prime}, augmenting one unit along it and its symmetric path gives an integral symmetric flow of larger value.

Theorem 10.

Given a unit-capacity skew-symmetric graph with maximum integral symmetric flow at least K, an algorithm can find a flow of value at least K/2 in n^(2+o(1)) time with high probability.

There exists an algorithm that, given a skew-symmetric graph G with unit capacity and a parameter K, assuming that the maximum integral symmetric flow of G is at least K, finds an integral symmetric flow of value at least \frac{K}{2} in n^{2+o(1)} time with high probability.

Lemma 11.

For an integral symmetric flow of value at least K/2 in residual graph G, the total charge on edges in the flow is negative.

For an integral symmetric flow f in G of value at least \frac{K}{2}, the total charge on edges in the flow is negative, i.e., \sum_{e}f_{e}d_{e}<0.

Lemma 15.

Quoted word for word from the full text on arXiv.

The paper

Maximum Cardinality Matching in n^(2+o(1)) Time

George Z. Li, Jason Li, Junkai Zhang

arXiv, Oct 29, 2026, Open access, CC BY, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.40591

arXiv:2610.40591v1 in cs.DS

AbstractPDFHTML

Cite as BibTeX
@misc{li2026maximum,
  title = {Maximum Cardinality Matching in $n^{2+o(1)}$ Time},
  author = {Li, George Z. and Li, Jason and Zhang, Junkai},
  year = {2026},
  eprint = {2610.40591},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arxiv.2610.40591},
  url = {https://arxiv.org/abs/2610.40591}
}

Related