Tutte Colloquium - Michael Anastos

Title: Finding perfect matchings in random regular graphs in linear expected time

Abstract:

In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results suggest that the first algorithm is superior. We show that this is indeed the case, at least for random regular graphs. We show that w.h.p. the first algorithm will find a matching of size n/2 - O(log n) on a random r-regular graph (r = O(1)). We also show that the algorithm can be adapted to find a perfect matching w.h.p. in O(n) time, as opposed to O(n^3/2) time for the worst-case. The case r = 3 is based on joint work with Alan Frieze
.