Approximating Maximum Matching Requires Almost Quadratic Time

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.