The cover polynomial and its geometric version introduced by Chung & Graham and D’Antona & Munarini, respectively, are two-variate
graph polynomials for directed graphs. They count the (weighted) number of ways to cover a graph with disjoint directed cycles
and paths, can be thought of as interpolations between determinant and permanent, and are proposed as directed analogues of
the Tutte polynomial.
Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #P-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomials:
We prove that, in almost the whole plane, the problem of evaluating the cover polynomial and its geometric version is #P-hard under polynomial time Turing reductions, while only three points in the cover polynomial and two points in the geometric
cover polynomial are easy. We also study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ≠ NP and RFP ≠ #P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within
any polynomial factor is not possible.
Keywords Graph polynomial – counting complexity – approximation – permanent – Tutte polynomial
Subject classification 68Q17 – 05C99