Beating Greedy Matching in Sublinear Time

We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a ( 1 2 + Ω(1))-approximation algorithm which can be implemented in O(n 1+ε ) time, where n is the number of vertices and the constant ε > 0 can be made arbitrarily small. The best known lower bound for the problem is Ω(n), which holds for any constant approximation.

Existing algorithms either obtain the greedy bound of 1 2 -approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in o(n 2 )-time [Yoshida, Yamamoto, and Ito STOC'09]. We improve over these by designing a less "adaptive" augmentation algorithm for maximum matching that might be of independent interest.