Sublinear Time Algorithms and Complexity of Approximate Maximum Matching

Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-approximation in O(n) time for n-vertex graphs. A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O(n1+є) time (for arbitrarily small constant ε>0). On the lower bound side, [Parnas and Ron; TCS’07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω(n) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then.