Tutte polynomials computable in polynomial time (Q686299): Difference between revisions

Determining the Tutte polynomial of a matroid at a fixed point \(P\) of the plane is known to be \(\# P\)-hard unless \(P\) lies on a certain hyperbola or is one of 8 special points (\textit{F. Jaeger}, \textit{D. L. Vertigan} and the second author [Math. Proc. Camb. Philos. Soc. 108, No. 1, 35-53 (1990; Zbl 0747.57006)]). The authors show that for any accessible class of matroids of bounded width, the Tutte polynomial is computable in polynomial time. Series-parallel matroids have this property (while the above \(\# P\)-hardness was proved for cycle matroids of planar graphs by Vertigan). The problem remains open for bounded tree-width.