期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
