Computational Complexity - Research Seminar
Christian Hoffmann: On the Complexity of the Interlace Polynomial
Feb. 19, 2008, 10:15 a.m.
E 1 3, Room 415
A graph polynomial is a mapping from graphs to polynomials such that p(G), the polynomial to which a graph G is mapped to, contains useful information about the graph G. In this talk, we will consider a new graph polynomial, the interlace polynomial (Arratia, Bollobas, Sorkin 2004). In particular I will introduce a graph transformation, vertex cloning, which is useful with the interlace polynomial. Using some nice tricks I will derive an identity which relates the interlace polynomial of a graph with cloned vertices to the interlace polynomial of the original graph. Using more interesting tricks, this will allow us to prove that at almost every point of the plane it is hard to evaluate the interlace polynomial, and that at many points it is even hard to approximate the interlace polynomial.