Approximating matchings in parallel (Q1261482)

A matching in an undirected graph \(G=(V,E)\) is a set \(M\subseteq E\) of edges such that no two edges of \(M\) share a vertex. The matching problem is to find a matching of maximum cardinality. This problem is not known to be in NC (solvable in polylog time using a polynomial number of processors) even for bipartite graphs except in certain special cases; the best results to date are sublinear-time algorithms [\textit{A. V. Goldberg}, \textit{S. A. Plotkin} and \textit{P. M. Vaidya}, J. Algorithms 14, No. 2, 180-213 (1993; Zbl 0769.68034)] and probabilistic algorithms [\textit{R. M. Karp}, \textit{E. Upful} and \textit{A. Wigderson}, Combinatorica 6, 35- 48 (1986; Zbl 0646.05051)]. The paper under review presents another compromise: can approximate algorithm which, for fixed \(k>0\), finds a matching with cardinality at last \(k/(k+1)\) times the maximum in \(O(k^ 4\log^ 3n)\) time using \(O(k_ n^{2k+2})\) processors on an \(n\)-vertex graph; with \(k\) constant this shows that approximating a maximum matching to within a constant factor is in NC. The model of parallel computation used is the exclusive-read, exclusive-write parallel random-access machine.