Simon Straub, Thomas Thierauf, and Fabian Wagner
Abstract:
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 K3,3-free graphs,
Vazirani showed that it is in NC2.
The technique there 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.