A combinatorial algorithm for Pfaffians
Let \(G\) be a graph on \(n\) vertices. With each edge \(ij\in G\), associate an indeterminate \(x_{ij}\) such that \(x_{ij}= -x_{ji}\). For even \(n\), let \(\mathcal{M}= |i_1i_2|i_3i_4|\cdots|i_{n-1}i_n|\) be a partition of the vertices of \(G\) into \(\frac{n}{2}\) unordered pairs; \(\mathcal{M}\) corresponds in a natural way to a possible perfect matching in \(G\). With each partition \(\mathcal{M}\) associate the permutation \[ \sigma_\mathcal{M}= \begin{pmatrix} 1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}. \] The Tutte matrix for \(G\) is an \(n\times n\) (skew symmetric) matrix \[ D = (d_{ij})= \begin{cases} x_{ij} & ij\in G \text{ and }i < j \\ x_{ji} & ij\in G \text{ and }i > j \\ 0 & \text{otherwise}. \end{cases} \] Then the Pfaffian of \(G\) is \[ \text{Pf}(G) = \text{Pf}(D) = \sum_{\mathcal{M}: \text{partition}} \operatorname {sgn}(\sigma_\mathcal{M})\cdot d_{i_1d_2}d_{i_3i_4}\cdots d_{i_{n-1}i_n}. \] The authors present the first combinatorial algorithm for computing the Pfaffian in polynomial time. In fact, they show that it can be computed in the complexity class GapL, the class of functions that can be expressed as the difference of the numbers of accepting paths of two nondeterministic logspace machines. As a corollary, they show that counting the number of perfect matchings in a planar graph is also in GapL. For the entire collection see [Zbl 0918.00033].
- On the theory of Pfaffian orientations. I: Perfect matchings and permanents
- On the computation of pfaffians
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- The complexity of planarity testing
- Counting the number of perfect matchings, and generalized decision trees
- Principal minors Pfaffian half-tree theorem
- scientific article; zbMATH DE number 741200 (Why is no real title available?)
- Faster Combinatorial Algorithms for Determinant and Pfaffian
- Counting over non-planar graphs
- Matchgate shadows for fermionic quantum simulation
- Matching signatures and Pfaffian graphs
- Faster combinatorial algorithms for determinant and Pfaffian
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
This page was built for publication: A combinatorial algorithm for Pfaffians
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938661)
