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.)