摘要：We study the maximum cardinality matching problem in a standard distributed setting, where the nodes V of a given n-node network graph G = (V,E) communicate over the edges E in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of G can send an O(log n)-bit message to each of its neighbors. We show that for every graph G and a matching M of G, there is a randomized CONGEST algorithm to verify M being a maximum matching of G in time O( M ) and disprove it in time O(D ð"), where D is the diameter of G and ð" is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time OÌf(s^*), where s^* is the size of a maximum matching.
