# Computing the Tutte polynomial on graphs of bounded clique-width

CS - FEI VŠB Ostrava, CZ

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.

#### Footnotes

- ...ý
^{1}
- joint work with Omer Gimenez and Marc Noy

2005-05-23