DIMACS TR: 99-39

A Combinatorial Algorithm for Pfaffians



Authors: Meena Mahajan, P. R. Subramanya and V. Vinay

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 completely combinatorial algorithm for computing the Pfaffian in polynomial time. Our algorithm works over arbitrary commutative rings. Over integers, we show that it can be computed in the complexity class GapL; this result was not known before. Our proof techniques generalize the recent Mahajan-Vinay combinatorial characterization of determinant in novel ways.

As a corollary, we show that under reasonable encodings of a planar graph, Kasteleyn's algorithm for counting the number of perfect matchings in a planar graph is also in GapL. The combinatorial characterization of Pfaffian also makes it possible to directly establish several algorithmic and complexity theoretic results on Perfect Matching which otherwise use determinants in a roundabout way.

We also present hardness results for computing the Pfaffian of an integer skew-symmetric matrix. We show that this is hard for #L and GapL under logspace many-one reductions.

Keywords: pfaffian, perfect matchings, determinant, planar graphs, GapL

Footnote: This work was initiated during the visit of the the third author.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-39.ps.gz
DIMACS Home Page