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

Abstract

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 point (x, y) ∈ Z2 that either T(G; x, y) can be computed in polynomial time, T(G; x, y) can be computed in 2O(tw)nO(1) time, but not in 2o(ctw)nO(1) time assuming the Exponential Time Hypothesis (ETH), T(G; x, y) can be computed in 2O(tw log tw)nO(1) time, but not in 2o(ctw log ctw)nO(1) time assuming the ETH, where we assume tree decompositions of treewidth tw and cutwidth decompositions of cutwidth ctw are given as input along with the input graph on n vertices and point (x, y). To obtain these results, we refine the existing reductions that were instrumental for the seminal dichotomy by Jaeger, Welsh and Vertigan [Math. Proc. Cambridge Philos. Soc’90]. One of our technical contributions is a new rank bound of a matrix that indicates whether the union of two forests is a forest itself, which we use to show that the number of forests of a graph can be counted in 2O(tw)nO(1) time.