论文标题
在密集图中计算完美匹配很难
Counting Perfect Matchings in Dense Graphs Is Hard
论文作者
论文摘要
我们表明，即使我们将输入限制在非常密集的图中，计算完美匹配的问题仍然是＃P-Complete，这证明了[5]中的猜想。在这里，“密集图”是指双方独立号的两部分图$ \ leq 2 $，或独立号码的一般图$ \ leq 2 $。我们的证明是通过基本线性代数技巧和图形结构来减少在两部分图中的完美匹配。
We show that the problem of counting perfect matchings remains #P-complete even if we restrict the input to very dense graphs, proving the conjecture in [5]. Here "dense graphs" refer to bipartite graphs of bipartite independence number $\leq 2$, or general graphs of independence number $\leq 2$. Our proof is by reduction from counting perfect matchings in bipartite graphs, via elementary linear algebra tricks and graph constructions.
