Combinatorial tools
Marek Karpiński, Wojciech Rytter · 1998
Abstract Recall that MatchNum(G) is the size (number of edges) of a maximum cardinality matching of a graph G = (V, E) and a perfect matching is a matching of size IVl/2. There are two basic combinatorial tools needed to compute this number: augmenting paths (to construct a matching of a maximal size k); witness sets (to provide an NC-proof that there is no matching of size larger thank). Almost all efficient sequential algorithms use augmenting paths, contrary to NC¬ algorithms. On the other hand witness sets are not used frequently in sequential computations but they are needed in parallel randomized computations. If an algorithm returns a matching of cardinality k then we are not certain if this cardinality is the maximum possible, even if there is a very small probability of failure. Our algorithm is a Monte Carlo algorithm. A better situation occurs when the algorithm provides a maximum cardinality matching and an easy (checkable in NC) proof that it is maximum. In this case the algorithm becomes the so-called Las Vegas algorithm. If a matching is perfect then it gives the optimality proof by itself.