CS Paper Radar

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

George Z. Li, Jason Li, Junkai Zhang

cs.DS ·submitted 2026-10-29 17:48 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Maximum Matching on Regular Nonbipartite Graphs

cs.DS cs.DM ·2026-09-12 ·Varsha Dani, Thomas P. Hayes, Seth Pettie
theory similarity 0.70
Abstract

Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in $O(m\sqrt{n})$ time, on both bipartite [HK73, Din70, Kar73a, Kar73a] and nonbipartite graphs [GT91, Gab17, Vaz24], but this time bound can be improved if the input is constrained. In this paper we consider $d$-regular bipartite and nonbipartite graphs. Previous algorithms show that a perfect matching in $d$-regular bipartite graphs can be computed in near-linear time deterministically [COS01] or sublinear time with high probability [GKK13]. On $d$-regular non-bipartite graphs, a $(1-1/(d+1))$-approximation can be computed in sublinear time $O(n \log n)$ with high probability [DH25], and hence a maximum matching can be computed in $O(n^2)$ time, w.h.p., which is slightly faster than the best deterministic algorithm for regular graphs [Yus13], running in O(n^2 log n) time. We prove that any blocking flow-type maximum matching algorithm based on finding shortest augmenting paths runs in $O(n^2)$ time on d-regular graphs, both bipartite and nonbipartite. On nonbipartite graphs this is an asymptotic improvement over $O(n^2 \log n)$ [Yus13] and an improvement over $O(m\sqrt{n})$ [GT91, Gab17, Vaz24] when $d = ω(\sqrt{n})$. It also improves [DH25] by making its $O(n^2)$ bound deterministic. However, the main take-away message is that no new algorithms are needed: the "classic" matching algorithms automatically outperform [Yus13, DH25]. We also consider extensions of our results to graphs that are only "nearly regular," meaning that their degrees all lie within a specified range, $[d, Δ]$.

0.24

A 2/3-Approximation Algorithm for the Residual Maximum Matching Problem in General Graphs

cs.DS ·2026-10-20 ·Quanlong Niu, Riheng Jia
theory similarity 0.69
Abstract

The residual maximum matching problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number. For unweighted graphs, previous work provides a $1/2$-approximation guarantee in general graphs and a $2/3$ guarantee in graphs with a perfect matching. We present a $2/3$-approximation algorithm running in $O(n^5)$ time, extending the latter guarantee to general graphs. The algorithm improves the residual matching number through single-edge exchanges involving free vertices. We prove that, for any maximum matching that admits no further improvement by such exchanges, the residual matching number is at least $2/3$ of the optimum, and we give an example showing that this bound is tight.

0.09

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.68
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

0.26

Degree Realization with Maximum Matching

cs.DM cs.DS ·2026-10-30 ·Amotz Bar-Noy, Igor Kalinichev, David Peleg, Dror Rawitz
similarity 0.66
Abstract

The Maximum Matching Degree Realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph(whose degree sequence corresponds to $d$) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence $d$ admits a realization with a matching of size $ν$ (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.

0.56

Fluid Limits and Upper Bounds for Randomized Greedy Matching

cs.DS math.CO ·2026-10-31 ·Sayan Mukherjee
theory similarity 0.65
Abstract

The Modified Randomized Greedy (MRG) algorithm [Tinhofer (1984), Aronson-Dyer-Frieze-Suen (1995)] is a classical greedy algorithm for finding approximate maximum matchings. MRG repeatedly picks a uniformly random unmatched vertex and matches it to a uniformly random unmatched neighbor, if one exists. Since 1991, the best upper bound on its approximation ratio has been $2/3$, given by the Bomb graphs of [Dyer and Frieze (1991)]. We improve this bound to $0.6569$ on general graphs and $0.6607$ on bipartite graphs. Our constructions consist of copies of small gadgets, with specified vertex classes joined completely. We track each algorithm by counting gadget copies with each possible configuration of remaining vertices. Wormald's differential equation method [Wormald (1995)] shows that these counts, scaled by the size parameter of the construction, converge to a deterministic trajectory known as the \textit{fluid limit}, which is described by ordinary differential equations. This fluid limit approximation holds while the relevant vertex classes have positive density, and so we devise a separate counting argument determines the contribution from the end of the run. Furthermore, we apply our framework to Random Decision Order (RDO), in which vertices are processed in uniformly random order and choose unmatched neighbors according to fixed adversarial preferences. On bipartite graphs, we determine the exact limiting ratio on the Double-Bomb family of [Tang-Wu-Zhang (2020)]. Its minimum is $31/48$, confirming their numerical estimate of about $0.646$.On general graphs, we improve their upper bound of $5/8$, given by the paw graph, to $0.5946$ on a new family. Finally, we give one possible explanation for why $2/3$ seemed to be optimal for MRG in the concluding remarks.

0.23

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework

cs.DS ·2026-11-01 ·Jiale Chen
similarity 0.65
Abstract · Abstract shortened due to arXiv requirements

We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.

0.16

A tight lower bound for malicious online bipartite matching with limited recourse budget

cs.DS cs.DM ·2026-08-23 ·Julia Baligacs, Bartłomiej Bosek, Paweł Putra, Marek Sokołowski, Anna Zych-Pawlewicz
theory similarity 0.64
Abstract

We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total number of reallocations, also known as the recourse budget. Despite extensive work, the exact recourse complexity of the problem remains unsettled: the best lower bound is $Ω(n \log n)$, whereas the best upper bound is $\mathcal{O}(n \log^2 n)$, where $n$ denotes the number of online vertices. Tight upper bounds of $\mathcal{O}(n \log n)$ are known only for restricted graph classes, such as forests. The best known upper bounds are attained by a very simple and natural algorithm SAP, which after each arrival applies a shortest augmenting path, and it is conjectured to be optimal. All known upper bound analyses of this algorithm do not depend on the particular maximum matching maintained by the algorithm. Consequently, they also apply to a more difficult problem, which we call the malicious matching setting: after each arrival, the maintained matching is replaced by a worst-case maximum matching for the next step. This led to the conjecture that the malicious setting still admits an $\mathcal{O}(n \log n)$ recourse bound, in line with the conjectured optimal complexity of the original model. Our main result is an $Ω(n \log^2 n)$ lower bound for the malicious matching setting, thus disproving the conjecture. Together with the previous upper bound, this settles the asymptotic recourse complexity of the malicious variant of the problem. We complement our lower bound with an upper bound of $\mathcal{O}(n \log n)$ for expander graphs.

0.20

A simplified proof of the FPRAS for counting perfect matchings

cs.DS math.CO ·2026-10-19 ·Chenghua Liu, Boning Meng
similarity 0.64
Abstract

We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.

0.26