Computational Complexity - Research Seminar
Christian Hoffmann: The "Local Trick" for Graph Polynomials
Nov. 8, 2007, 10:15 a.m.
E 1 3, Room 415
Several ad-hoc techniques have been employed to analyze the computational complexity of evaluating graph polynomials. One such technique is to perform a simple operation on all "pieces" (vertices, edges, ...) of the graph, which "magically" yields interesting identities for the respective graph polynomial. This "local trick" has turned out to be helpful with the Tutte polynomial on the one hand and the interlace polynomial on the other hand. Although it is intuitively obvious that in both cases the same idea is used, the concrete proofs argue about different objects and differ in other technical details. The aim of the talk is to discuss how the local trick could be generalized such that we get a better understanding why it works and what conditions have to be fulfilled if we want to use it.