Counting the Number of Perfect Matchings, and Generalized Decision Trees.

We consider a generalization of the Pólya–Kasteleyn approach to counting the number of perfect matchings in a graph based on computing the symbolic Pfaffian of a directed adjacency matrix of the graph. Complexity of algorithms based on this approach is related to the complexity of the sign function of a perfect matching in generalized decision tree models. We obtain lower bounds on the complexity of the sign of a perfect matching in terms of the deterministic communication complexity of the XOR sign function of a matching. These bounds demonstrate limitations of the symbolic Pfaffian method for both the general case and the case of sparse graphs. [ABSTRACT FROM AUTHOR]