The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree

The cover polynomials are bivariate graph polynomials that can be defined as weighted sums over all path-cycle covers of a graph. In [3], a dichotomy result for the cover polynomials was proven, establishing that their evaluation is #P-hard everywhere but at a finite set of points, where evaluation is in FP. In this paper, we show that almost the same dichotomy holds when restricting the evaluation to planar graphs. We even provide hardness results for planar DAGs of bounded degree. For particular subclasses of planar graphs of bounded degree and for variants thereof, we also provide algorithms that allow for polynomial-time evaluation of the cover polynomials at certain new points by utilizing Valiant's holographic framework.