Counting the Number of Perfect Matchings in K5-Free Graphs

Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K5-free graphs, this technique will not work because some K5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K5-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC2. We remark that our results generalize to graphs without singly-crossing minor.