Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V


The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC
Dima Grigoriev and Marek Karpinski
[Download PostScript] [Download PDF]

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = nO(1)) are in the deterministic classes NC2 and NC3, respectively. We further design an NC3 algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(nk). The basic step was the development of a new symmetric function method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3n) parallel time and O(n3k+5.5 log n) processors. It entails among other things an efficient NC3-algorithm for computing small (polynomial bounded) arithmetic permanents and a sublinear parallel time algorithm for the bipartite matching with permanents up to 2nc.
Concerning the circuit complexity of the logical permanent (cf. [Ra 85]), we display a class of bounded permanent problems, each of superpolynomial monotone circuit complexity nΩ(log n)([Ra 85]), and which are computable within the uniform O(log2 n) depth and O(n4.5) size boolean circuits.

Last Change: 12/01/08 at 17:22:36
University of Bonn -> Department of Computer Science -> Chair V