The combinatorial approach yields an NC algorithm for computing Pfaffians

Mahajan, Meena ; Subramanya, P.R. ; Vinay, V. (2004) The combinatorial approach yields an NC algorithm for computing Pfaffians Discrete Applied Mathematics, 143 (1-3). pp. 1-16. ISSN 0166-218X

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier B.V.
Keywords:Pfaffian; Matching; Combinatorics; Algorithm; NC
ID Code:127993
Deposited On:14 Oct 2022 11:30
Last Modified:14 Oct 2022 11:30

Repository Staff Only: item control page