A breakthrough sequence of papers by Goel, Kapralov, and Khanna gave the first sublinear-time algorithms for finding large matchings in regular bipartite graphs. The crown jewel of these is an $O(n \log n)$ algorithm to find a perfect matching, based on the idea of randomly generated augmenting paths.
We discuss the extent to which the restrictions of being regular and bipartite can be relaxed. In particular, we will show that, for all d-regular (non-bipartite) graphs, a matching using a (1-1/(d+1)) fraction of the vertices can be found in O(n log d) time. At the heart of our algorithm is a new method for turning walks that alternate between matching and non-matching edges into alternating paths.
