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


Abstract

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