Sublinear Algorithms for (1.5+ε)-Approximate Matching

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. [SODA'23] improved the approximation factor to (2 - 1/2(O) (1/gamma)) using n(1+gamma) time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n(2-Omega(1)) time. We give a strong affirmative answer to this open problem by showing (1.5 + epsilon)-approximation algorithms that run in n(2)-Theta(epsilon(2)) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and streaming [Bernstein ICALP'20] settings, but never before in the sublinear setting.