Computational complexity of graph polynomials
Hoffmann, Christian · 2010
provides hardness and algorithmic results for graph polynomials. We observe VNP-completeness of the interlace polynomial, and we prove VNP-completeness of almost all q-restrictions of Z(G; q,x), the multivariate Tutte poly-nomial. Using graph transformations, we obtain point-to-point reductions for graph poly-nomials. We develop two general methods: Vertex/edge cloning and, more gen-eral, uniform local graph transformations. These methods unify known and new hardness-of-evaluation results for graph polynomials. We apply both methods to several examples. We show that, almost everywhere, it is #P-hard to evaluate the two-variable interlace polynomial and the (normal as well as extended) bivariate chromatic polynomial. “Almost everywhere ” means that the dimension of the set of exceptional points is strictly less than the dimension of the domain of the graph polynomial. We also give an inapproximability result for evaluation of the inde-pendent set polynomial. Providing a new family of reductions for the interlace polynomial that increases the instance size only polylogarithmically, we obtain an