Efficient computation of generalized Ising polynomials on graphs with fixed clique-width

Tomer Kotek, Johann A. Makowsky

Graph polynomials which are definable in Monadic Second Order Logic (MSOL) on the vocabulary of graphs are Fixed-Parameter Tractable (FPT) with respect to clique-width. In contrast…