Improved processor bounds for combinatorial problems in RNC (Q1262128)

A perfect matching of a graph G is a set of edges in G such that each vertex of G appears in exactly one edge of the set. The paper studies the computational complexity of finding a perfect matching in parallel. In (KUW), a randomized parallel algorithm of time complexity \(O(\log^ 3n)\) that uses \(O(n^ 4M(n))\) processors has been designed. Here n denotes the number of vertices of the input graph and M(n) denotes the best sequential arithmetic time for \(n\times n\) matrix multiplication. This paper shows that the number of processors can be significantly reduced (by a factor of \(n^ 4)\) while maintaining the expected running time. The new algorithm is a sophisticated implementation of the method used in [\textit{R. M. Karp}, \textit{E. Upfal} and \textit{A. Wigderson}, Constructing a perfect matching is in random NC, Combinatorica 6, 35-48 (1986; Zbl 0646.05051)]. In particular, it reduces each iteration of the algorithm to computing the inverse and the determinant of an \(n\times n\) integer matrix with bounded entry lengths. The improved solution to the perfect matching problem leads to more efficient parallel algorithms for several related combinatorial problems.