Analysis of a randomized greedy matching algorithm
ALAN M. FRIEZE, Jonathan Aronson · 1995
Polynomial time algorithms for finding the maximum matching in a graph have existed since 1965. Recently work has been done on randomized greedy algorithms for finding large matchings in graphs in linear time. The algorithm considered here takes a graph and removes a random leaf along with its neighbors. The leaf is put into the matching. If no leaf exists then a random edge is chosen instead. Phase I ends and Phase II begins when for the first time there are no leaves. Let $c>0$ be a constant and let $p={c\over n}.$ Karp and Sipser studied this algorithm when run on a random graph from $G\sb{n,p}.$ They proved that the algorithm performs optimally during Phase I. When $ce$ then w.h.p. the size of the remainder is r(c)n for some constant r(c). In Phase II, o(n) vertices are left unused w.h.p. In this paper the algorithm is analyzed when run on a random graph from $G\sb{n,m}.$ Here $m = {cn\over2}.$ Let $\gamma$ be the unique solution to $\gamma=c {\rm exp}(-\gamma).$ Let $\gamma\sb{o}$ be the smallest solution to $\gamma = c {\rm exp}(-c {\rm exp}(-\gamma))$ and let $\gamma\sb{e} = c {\rm exp}(-\gamma\sb{o}).$ Different behavior occurs for $ce.$ For $ce,$ the algorithm loses between $\Omega(n\sp{{1\over18}{-}\epsilon})$ and $O(n\sp{{2\over3}+\epsilon})$ vertices for any $\epsilon>0.$ For $c>e$ the size of the matching produced is ${n\over c}(c -{1\over2}(\gamma\sb{e}+\gamma\sb{o}+\gamma\sb{e}\gamma\sb{o}))(1 + o(1)).$ For $c