On the Counting Complexity of the Cover Polynomial for Simple Graphs
摘要
Graph polynomials are graph invariants that map graphs to polynomials. As an analogue of the famous Tutte polynomial for directed graphs, Chung and Graham (J. Comb. Theory Series B 65(2):273–290, 1995) define the cover polynomial \(C_G(x,y)\) . Bläser and Dell (Automata, Languages and Programming, pp. 801–812. Springer, Berlin, 2007) prove that evaluating the cover polynomial is \(\#\mathsf {P}\) -hard, except for the points \((0,0),(0,-1),(1,-1)\) . There the evaluation is easy. However, the graphs used in this reduction are not simple. Motivated by a connection between the cover polynomial and the drop polynomial for simple graphs, Chung and Graham (J. Comb. Theory Series B 126:62–82, 2017) conjecture that the cover polynomial is also hard when restricted to simple graphs (which do not allow parallel edges or loops). As our main result, we confirm this conjecture.