Beating Greedy Matching in Sublinear Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi · Society for Industrial and Applied Mathematics eBooks · 2023
We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a (½ + Ω(1))-approximation algorithm which can be implemented in O(n1+ε) 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 ½-approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in o(n2)-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.