A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs

A breakthrough pair of papers by Goel, Kapralov, and Khanna [9, 8] gave the first sublinear-time algorithms for finding large matchings in regular bipartite graphs. In particular, they gave an algorithm based on the idea of randomized depth-first search, that, for any d-regular bipartite graph, finds a perfect matching in O(n log n) time. (When d = ω(log n), this is sublinear in the size of the graph.) We investigate whether large matchings can still be found without the assumption of bipartiteness. On the positive side, we present a randomized algorithm that finds a matching whose size is at least ⌈ⁿ₂ (1− _d+1¹ )− _log¹_n ⌉ on any d-regular graph, and whose expected running time is O(n log n). As is well known, there exist non-bipartite d-regular graphs whose maximal matching has size only ⁿ₂ (1 − _d+1¹ ). Moreover, even when larger matchings do exist, we prove that they cannot, in general, be found in sublinear time. Specifically, we prove the lower bound: for all ε > 0, all d = d(n), every algorithm that, given a d-regular graph G, outputs a matching whose size is at least 1− _d¹⁻₊₁^ε times the maximum matching size for G, must have expected running time Ω(dn) on worst-case inputs. Thus, in a certain precise sense, 1 − 1/(d + 1) is the approximation threshold for maximum matching in sublinear time.