  For a graph G=(V,E), finding a set of disjoint edges that do not share any
vertices is called a matching problem, and finding the maximum matching is a
fundamental problem in the theory of distributed graph algorithms. Although
local algorithms for the approximate maximum matching problem have been widely
studied, exact algorithms has not been much studied. In fact, no exact maximum
matching algorithm that is faster than the trivial upper bound of O(n^2) rounds
is known for the general instance. In this paper, we propose a randomized
O(s_{max}^{3/2}+log n)-round algorithm in the CONGEST model, where s_{\max} is
the size of maximum matching. This is the first exact maximum matching
algorithm in o(n^2) rounds for general instances in the CONGEST model. The key
technical ingredient of our result is a distributed algorithms of finding an
augmenting path in O(s_{\max}) rounds, which is based on a novel technique of
constructing a sparse certificate of augmenting paths, which is a subgraph of
the input graph preserving at least one augmenting path. To establish a highly
parallel construction of sparse certificates, we also propose a new
characterization of sparse certificates, which might also be of independent
interest.
