Computing the Tutte polynomial on graphs of bounded clique-width

Peter Hliněný¹

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 $P_4$), and it is a more general notion than that of tree-width. We show a subexponential algorithm (running in time $\exp{O(n^{1-\varepsilon})}\,$) for computing the Tutte polynomial on graphs of bounded clique-width. In fact, our algorithm computes the so-called $U$ polynomial of such a graph.

Footnotes

...ý¹

joint work with Omer Gimenez and Marc Noy