Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




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.