The exact complexity of the Tutte polynomial
Tomer Kotek, Johann A. Makowsky · 2022
In this chapter we explore the complexity of exactly computing the Tutte polynomial and its evaluations for graphs and matroids in various models of computation. The Turing complexity of evaluating the Tutte polynomial exactly and the resulting dichotomy theorem. The special case of planar and bipartite planar graphs. The impact of various kinds of graph width (tree-width, clique-width, branch-width) on computing the Tutte polynomial. The role of encoding matroids as inputs for computing the Tutte polynomial: Turing complexity for succinct presentations of matroids versus matroid oracles. The complexity in algebraic models of computation: Valiant&s;s uniform families of algebraic circuits and the computational model of Blum–Shub–Smale (BSS).