ECCC-Report TR14-079https://eccc.weizmann.ac.il/report/2014/079Comments and Revisions published for TR14-079en-usWed, 11 Jun 2014 16:29:27 +0300
Paper TR14-079
| Counting the Number of Perfect Matchings in $K_5$-free Graphs |
Thomas Thierauf,
Simon Straub,
Fabian Wagner
https://eccc.weizmann.ac.il/report/2014/079Counting 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$^2$. The technique there is to compute a Pfaffian orientation of a graph.
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$.Wed, 11 Jun 2014 16:29:27 +0300https://eccc.weizmann.ac.il/report/2014/079