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

In the case of *K*_{5}-free graphs,
this technique will not work because some *K*_{5}-free graphs
do not have a Pfaffian orientation.
We circumvent this problem and show that
the number of perfect matchings in *K*_{5}-free graphs
can be computed in polynomial time.
We also parallelize the sequential algorithm and show that the problem is in TC^{2}.