Random parallel algorithms for finding exact branchings, perfect matchings, and cycles

In this paper we devise randomized parallel algorithms which given a unary weighted (di)graph G=(V, E)construct in time O(log2| V|) branchings, perfect matchings, and disjoint cycles of weight exactly k belonging to G. These problems have been studied by Papadimitriou and Yannakakis [PY1], by Barahona and Pulleyblank [BP], by Camerini et al [CGM], and by Mulmuley et al. [MVV]. Our algorithms improve previous solutions. Moreover, we give an NC2 algorithm for computing the absolute value of the pfaffian of a skew-symmetric matrix.