Farrell polynomials on graphs of bounded tree width

J.A. Makowsky and J.P. Marino

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


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 in combinatorics, but also in physics, chemistry and biology. In general the worst case complexity of most these polynomials is known to be {\bf NP}, or even $\sharp \mathbf{P}$ hard. We show that such polynomials characterized by a definability condition in the formalisms of Monadic Second Order Logic can be computed in polynomial time if restricted to graphs of tree width at most $k$.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:03
Maintainer maylis@labri.u-bordeaux.fr.
Start Conference Manager
Conference Systems