Peter Hliněný1
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 cograhs (graphs without induced ), and it is a more
general notion than that of tree-width. We show a subexponential algorithm
(running in time
) for computing the Tutte
polynomial on graphs of bounded clique-width. In fact, our algorithm
computes the so-called
polynomial of such a graph.