# Computational Complexity - Research Seminar

## Christian Hoffmann: *Computing the Interlace Polynomial Using Tree Decompositions*

Oct. 30, 2008, 10:15 a.m.

E 1 3, Room 415

Computing the interlace polynomial of a graph is a #P-hard problem in general. If restricted to graphs of bounded treewidth it can be solved in polynomial time. This follows from the work of Courcelle using a general framwork, monadic second order logic (MSOL) for graph polynomials. As this is a general approach working for any MSOL definable graph polynomial, it does not use specific properties of the interlace polynomial and leads to a bad running time (doubly exponential in the tree width).

I will present a new algorithm to compute the interlace polynomial using tree decompositions. This algorithm is not based on MSOL, but computes the interlace polynomial directly. The running time is 2^O(*k*^{2}) ⋅ *n*, where *n* is the number of vertices of the input graph *G* and *k* is the width of a tree decomposition of *G*.