Abstract:
Tutte polynomials are important graph invariants with rich applications in combinatorics, topology, coding theory and even physics. The Tutte polynomial $T(G,X,Y)$ is a polynomial in $\mathbb{Z}[X,Y]$ which depends on a graph $G$. Computing the coefficients of $T(G,X,Y)$, and even evaluating $T(G,X,Y)$ at specific points $(x,y)$ is $\sharp \bP$ hard by a result of Jaeger, Vertigan and Welsh, (1990). On the other hand, if $G$ is a graph of bounded tree width, computing $T(G,X,Y)$ can be done in polynomial time (Andrzejak, 1998), and evaluation even in linear time (Noble, 1998). We extend this result to the colored Tutte polynomials introduced in 1999 by Bollobas and Riordan.

Jones polynomials and Kauffman polynomials are the most prominent invariants of knot theory. For alternating links, they are easily computable from the Tutte polynomials by a result of Thistlethwaite (1988). Knots and links can be presented as labeled planar graphs. The tree width of a link $L$ is defined as the tree width of its graphical presentation $D(L)$ as crossing diagrams. We show that for (not necessarily alternating) knots and links of tree width at most $k$, even the Kauffman square bracket $[L]$ introduced by Bollobas and Riordan can be computed in polynomial time. Hence, the classical Kauffman bracket $\langle L \rangle$ and the Jones polynomial of links of tree width at most $k$ are computable in polynomial time.

Our proof is based on but extends considerably previous work by B. Courcelle, U. Rotics and the author. It also gives a new proof of the result for Tutte polynomials and generalizes to a wide class of polynomials defined as generating functions definable in Monadic Second Order Logic with order, but invariant under it.