Counting the Number of Perfect Matchings in K5-Free Graphs

Counting the number of perfect matchings in arbitrary graphs is a #P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for K_3,3-free graphs, Vazirani showed that it is in NC². The technique there is to compute a Pfaffian orientation of a graph. In the case of K₅-free graphs, this technique will not work because some K₅-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K₅-free graphs can be computed in polynomial time and we describe a circuit construction in TC².