Maximum matchings in sparse random graphs: Karp–Sipser revisited

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph Gn, c/n, where c>0 is constant. The algorithm was first proposed by Karp and Sipser [Proceedings of the Twenty-Second Annual IEEE Symposium on Foundations of Computing, 1981, pp. 364–375]. We give significantly improved estimates of the errors made by the algorithm. For the subcritical case where c<e we show that the algorithm finds a maximum matching with high probability. If c>e then with high probability the algorithm produces a matching which is within n1/5+o(1) of maximum size.