Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-030 | 9th July 1999 00:00

A Combinatorial Algorithm for Pfaffians


Authors: Meena Mahajan, P R Subramanya, V Vinay
Publication: 3rd September 1999 08:05
Downloads: 3953


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.

ISSN 1433-8092 | Imprint