# Computational Complexity - Research Seminar

## Holger Dell: *The Tutte Polynomial and Its Complexity*

June 28, 2006, 10:15 a.m.

E 1 3, Room 415

A graph polynomial is a mapping that maps graphs to a polynomial such that isomorphic graphs are mapped to the same polynomial. The Tutte polynomial is a well-studied bivariate graph polynomial which encodes many interesting information about the graph, such as the number of spanning trees or the number of c-colourings. Therefore, the Tutte polynomial encodes NP-complete information, and its evaluation cannot be easy everywhere.

We reduce the evalutation of the whole Tutte polynomial to its evaluation at any fixed non-special point by using streching, thickening and colouring reductions and Lagrange interpolation. This proves that the evaluation of the Tutte polynomial is #P-hard at all but a few special points.