Farrell polynomials on graphs of bounded tree width

We consider various classes of graph polynomials and study their computational complexity. Our main focus is on Farrell polynomials and generating functions of graph properties. All these polynomials have a wide range of applications in combinatorics, but also in physics, chemistry, and biology. In general, the worst-case complexity of most these polynomials is known to be NP-hard, or even #P-hard. We show that, if these polynomials satisfy a definability condition in the formalisms of monadic second-order logic, then they can be computed in polynomial time if restricted to graphs of tree width at most k. In other words, they are fixed-parameter tractable (FPT) with parameter the tree width of the input graph. (C) 2003 Elsevier Science (USA). All rights reserved.