Matching is as easy as matrix inversion (Q1095658)

This paper presents a randomized parallel algorithm which finds a maximum matching in an n-vertex m-edge graph in \(O(\log^ 2 n)\) time using \(O(n^{3.5} m)\) processors. This result improves upon the \(RNC^ 2\) algorithm of \textit{L. Lovasz} [Fundamentals of computation theory '79, Proc. Conf., Berlin/Wendisch-Rietz 1979, 565-574 (1979; Zbl 0446.68036)] for deciding if a graph has a perfect matching, and the \(RNC^ 3\) algorithm of \textit{R. M. Karp}, \textit{E. Uppal} and \textit{A. Wigderson} [Finding a maximum matching is in random NC, Seventeenth Annual Symp. on Theory of Computing (1985)]. Other results presented include \(RNC^ 2\) algorithms for vertex-weighted matching and exact matching (a perfect matching which uses exactly k edges from a given edge-subset - a problem for which no deterministic polynomial algorithm is known), and a simpler proof of a theorem first proved by \textit{L. G. Valiant} and \textit{V. V. Vazrani} [Theor. Comput. Sci. 47, 85-95 (1986; Zbl 0621.68030)]. These results follow from Tutte's theorem relating the existence of a perfect matching to the invertibility of a certain \(n\times n\) matrix [\textit{W. T. Tutte}, J. Lond. Math. Soc. 22, 107-111 (1947; Zbl 0029.23301)], Pan's \(RNC^ 2\) matrix-inversion algorithm [\textit{V. Pan}, Lect. Notes Comput. Sci. 206, 504-521 (1985; Zbl 0598.68042)] and the ``isolating lemma'' introduced in the present paper: if S is a set of n elements, each of which is assigned an integer weight at random from [1,2n], and F is a family of subsets of S, then the probability that F has a unique minimum-weight set is at least 0.5.