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.