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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Counting Complexity of the Cover Polynomial for Simple Graphs

  • Markus Bläser,
  • Nico Mansion

摘要

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.