On the Fixed Parameter Complexity of Graph Enumeration Problems Definable in Monadic Second Order Logic

B. Courcelle, J. Makowsky and U. Rotics

We discuss the parametrized complexity of enumeration and evaluation problems on graphs definable in Monadic Second Order Logic. We show that for fixed tree width, these problems are solvable in polynomial time. The same holds for fixed clique width in the cases where the clique decomposition can be computed in polynomial time. As applications we discuss in detail how this affects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL definable graph properties, including $SAT$ and $\sharp SAT$.