Complexity of the Cover Polynomial
Complexity of the Cover Polynomial
复制标题
覆盖多项式的复杂度
DOI：
10.1007/978-3-540-73420-8_69
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Holger Dell
中科院分区：
文献类型：
--
作者：
Markus Bläser;Holger Dell
Chung和Graham提出的覆盖多项式是有向图的二元图多项式。它计算了覆盖一个具有不相交有向圈和路径的图的（加权）方法的数量，它是行列式和永久式之间的插值，并且被认为是Tutte多项式的有向模拟。Jaeger，Vertigan和Welsh证明了Tutte多项式除了一些特殊的点和曲线外，很难计算。事实证明，同样适用于覆盖多项式：我们证明，在几乎整个平面上，计算覆盖多项式的问题在多项式时间图灵约简下是#Phard，而只有三点是容易的。我们的构造使用了一个小工具，它比Valiant在证明永久式是#P-完全时使用的XOR小工具更容易分析，也更一般。
The cover polynomial introduced by Chung and Graham is a two-variate graph polynomial for directed graphs. It counts the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, it is an interpolation between determinant and permanent, and it is believed to be a directed analogue of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #Phard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomial: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial is #Phard under polynomial-time Turing reductions, while only three points are easy. Our construction uses a gadget which is easier to analyze and more general than the XOR-gadget used by Valiant in his proof that the permanent is #P-complete.