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

arXiv:2610.40591 · cs.DS · Submitted 2026-10-29 · Read on arXiv

cs.DS

Submitted: 2026-10-29

Updated: 2026-10-29

License: http://creativecommons.org/licenses/by/4.0/

The gist: We consider the maximum cardinality matching problem in general graphs, and give an n 2+o(1) -time algorithm for the problem.

Abstract

We consider the maximum cardinality matching problem in general graphs, and give an n 2+o(1) -time algorithm for the problem. Our work builds on recent work on combinatorial algorithms for maximum flow and extends the techniques to skew-symmetric flow problems which capture general matchings as a special case.

Related papers