Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width

International audienceGraph polynomials which are definable in Monadic Second Order Logic ($\mathrm {MSOL}$) on the vocabulary of graphs are Fixed-Parameter Tractable ($\mathrm {FPT}$) with respect to clique-width. In contrast, graph polynomials which are definable in $\mathrm {MSOL}$ on the vocabulary of hypergraphs are fixed-parameter tractable with respect to tree-width, but not necessarily with respect to clique-width. No algorithmic meta-theorem is known for the computation of graph polynomials definable in $\mathrm {MSOL}$ on the vocabulary of hypergraphs with respect to clique-width. We define an infinite class of such graph polynomials extending the class of graph polynomials definable in $\mathrm {MSOL}$ on the vocabulary of graphs and prove that they are Fixed-Parameter Polynomial Time ($\mathrm {FPPT}$ or $\mathrm {XP}$) computable, i.e. that they can be computed in time $O(n^{f(k)})$, where n is the number of vertices and k is the clique-width