Authors: Markus Bläser Christian Hoffmann
Publish Date: 2010/08/06
Volume: 61, Issue: 1, Pages: 3-35
Abstract
We consider the multivariate interlace polynomial introduced by Courcelle Electron J Comb 151 2008 which generalizes several interlace polynomials defined by Arratia Bollobás and Sorkin J Comb Theory Ser B 922199–233 2004 and by Aigner and van der Holst Linear Algebra Appl 2004 We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k The best previously known result Courcelle Electron J Comb 151 2008 employs a general logical framework and leads to an algorithm with running time fk⋅n where fk is doubly exponential in k Analyzing the GF2rank of adjacency matrices in the context of tree decompositions we give a faster and more direct algorithm Our algorithm uses 23k2+Okcdot n arithmetic operations and can be efficiently implemented in parallel
Keywords: