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(k2) ⋅ n, where n is the number of vertices of the input graph G and k is the width of a tree decomposition of G.