Maximum Cardinality Matching in n 2+o(1) Time
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles