The combinatorial approach yields an NC algorithm for computing Pfaffians

Abstract

The Pfaffian of an oriented graph is closely linked to perfect matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and determinant is usually exploited to give a fast algorithm for computing Pfaffians. We present the first NC algorithm for computing the Pfaffian. (Previous determinant-based methods computed it in NC only up to the correct sign, while previous polynomial-time algorithms did not lend themselves to parallelization.) Our algorithm is completely combinatorial in nature. Furthermore, it is division-free and works over arbitrary commutative rings. Over integers, we show that it can be implemented in the complexity class GapL. This upper bound was not known before, and establishes that computing the Pfaffian for integer skew-symmetric matrices is complete for GapL. Our proof techniques generalize the recent combinatorial characterization of determinant Proceedings of the Eighth Annual ACM-SIAM Symposium o Discrete Algorithms, SODA, 1997, 730. As a corollary, we show that under reasonable encodings of a planar graph, Kasteleyn's algorithm [Graph Theory and Theoretical Physics, Academic Press, New York, 1967, 43] for counting the number of perfect matchings in a planar graph is also in GapL.