论文标题
在平面图中计数最大匹配很难
Counting Maximum Matchings in Planar Graphs Is Hard
论文作者
论文摘要
在这里，我们证明，在平面中计算最大匹配，两部分图是＃p-complete。这有些令人惊讶的是，可以在多项式时间内计算平面图中的完美匹配数量。我们还证明，如果问题仅限于两部分图，则在平面图中计数非必要的完美匹配已经是＃P-Complete。到目前为止，硬度仅适用于一般的，非必要的两分图。
Here we prove that counting maximum matchings in planar, bipartite graphs is #P-complete. This is somewhat surprising in the light that the number of perfect matchings in planar graphs can be computed in polynomial time. We also prove that counting non-necessarily perfect matchings in planar graphs is already #P-complete if the problem is restricted to bipartite graphs. So far hardness was proved only for general, non-necessarily bipartite graphs.
