| Abstract: | We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ? such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ?. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs. |
