Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
Omer Giménez, Petr Hliněný, Marc Noy · SIAM Journal on Discrete Mathematics · 2006
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 $\exp{O(n^{1-\varepsilon})}\,$) for computing the Tutte polynomial on graphs of bounded clique‐width. In fact, our algorithm computes the more general U‐polynomial.