Counting the Number of Perfect Matchings in K5-Free Graphs
Counting the Number of Perfect Matchings in K5-Free Graphs
复制标题
DOI：
10.1007/s00224-015-9645-1
复制
发表时间：
2014-06
影响因子：
0.5
通讯作者：
Simon Straub;T. Thierauf;Fabian Wagner
中科院分区：
文献类型：
--
作者：
Simon Straub;T. Thierauf;Fabian Wagner
计算图中完美匹配的个数是一个计算困难的问题。然而，在平面图的情况下，甚至对于K3，3-Free图，完全匹配的数目可以有效地计算出来。实现这一点的技术是计算图的Pfaffian方向。在没有K5的图的情况下，这种技术不起作用，因为一些没有K5的图没有Pfaffian方向。我们绕过了这个问题，证明了K5-Free图的完美匹配数可以在多项式时间内计算出来。我们还对序列算法进行了并行化，证明了问题存在于TC2中。我们注意到，我们的结果推广到没有单交子图的图。
Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even forK3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute aPfaffian orientationof a graph. In the case ofK5-free graphs, this technique will not work because someK5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings inK5-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.