Tutte seminar - Alan Frieze

The Karp-Sipser Matching Algorithm and Refinements

Abstract:

Karp and Sipser (1981) proposed a simple greedy matching algorithm that they showed to work surprisingly well on sparse random graphs. In addition they showed a remarkable transition in the algorithm's performance at average degree e=2.718.... . In 1998 Aronson,F,Pittel gave a sharper analysis and I will try to give a quick overview of this. More recently, Bohman and F. have applied the algorithm to random graphs with a fixed degree sequence satisfying a log-concavity condition. We describe how this condition enables one to analyse the K-S algorithm in this context. Finally, A,F,P had shown that whp K-S only makes very few "mistakes" and this raises the possibility of fixing these mistakes via an augmenting path algorithm in o(n) time, making O(n) time altogether. We show how this can be done, in joint work with P. Chebolu and P. Melsted.