AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

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.

Bodo Manthey

5502

--email hidden

passcode not visible

logged in users only