A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth

Isja Mannens, Jesper Nederlof

We give a fine-grained classification of evaluating the Tutte polynomial $T(G;x,y)$ on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any…