We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobas, and Sorkin (J. Comb. Theory Ser. B 92(2):199---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. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)?n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses @math arithmetic operations and can be efficiently implemented in parallel.
The monadic second order logic approach is very general and can be applied not only to the interlace polynomial but to a much wider class of graph polynomials @cite_24 . However, it does not consider characteristic properties of the actual graph polynomial. In this paper, we restrict ourselves to the interlace polynomial so as to exploit its specific properties and to gain a more efficient algorithm (Algorithm ). Our algorithm performs @math arithmetic operations to evaluate Courcelle's multivariate interlace polynomial (and thus any other version of the interlace polynomial mentioned above) on an @math -vertex graph given a tree decomposition of width @math (Theorem ). The algorithm can be implemented in parallel using depth polylogarithmic in @math (). Apart from evaluating the interlace polynomial, our approach can also be used to compute coefficients of the interlace polynomial, for example so called @math -truncations [Section 5] courcelle_interlace_final (). Our approach is not via logic but via the @math -rank of adjacency matrices, which is specific to the interlace polynomial.
@cite_24
2109716789
We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is denable in monadic second-order logic (MSOL). We show that for bounded tree-width these problems are solvable in polynomial time. The same holds for bounded clique width in the cases, where the decomposition, which establishes the bound on the clique-width, can be computed in polynomial time and for problems expressible by monadic second-order formulas without edge set quantication. Such quantications are allowed in the case of graphs with bounded tree-width. As applications we discuss in detail how this aects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL denable graph properties. Finally, our results are also applicable to SAT and ]SAT. ? 2001 Elsevier Science B.V. All rights reserved.