Computing the tutte polynomial on graphs of bounded clique-width

The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion of clique-width extends the definition of cographs ( graphs without induced P-4), and it is a more general notion than that of tree-width. We show a subexponential algorithm ( running in time expO(n(1-epsilon))) for computing the Tutte polynomial on graphs of bounded clique- width. In fact, our algorithm computes the more general U-polynomial.