A las vegas rnc algorithm for maximum matching

Recently two randomized algorithms were discovered that find a maximum matching in an arbitrary graph in polylog time, when run on a parallel random access machine. Both are Monte Carlo algorithms — they have the drawback that with non-zero probability the output is a non-maximum matching. We use the min-max formula for the size of a maximum matching to convert any Monte Carlo maximum matching algorithm into a Las Vegas (error-free) one. The resulting algorithm returns (with high probability) a maximum matching and a certificate proving that the matching is indeed maximum. Research supported by DARPA grant N00039-84-C-0098 and by a US Army Research Office fellowship.