# Approximating Maximum Matching Requires Almost Quadratic Time

arXiv: https://arxiv.org/abs/2406.08595 · HTML: https://mlsanity.com/paper/2406.08595/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For n-vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS'23] (BKS) showed that an estimate that is within varepsilon n of the optimal solution can be achieved in n2-Omega_varepsilon(1) time, where n is the number of vertices. While this is subquadratic in n for any fixed varepsilon > 0, it gets closer and closer to the trivial Theta(n2) time algorithm that reads the entire input as varepsilon is made smaller and smaller. In this work, we close this gap and show that the algorithm of BKS is close to optimal. In particular, we prove that for any fixed δ > 0, there is another fixed varepsilon = varepsilon(δ) > 0 such that estimating the size of maximum matching within an additive error of varepsilon n requires Omega(n2-δ) time in the adjacency list model.