Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width

Abstract

We show that for any $k$ there is a polynomial time algorithm to evaluate the weighted graph polynomial $U$ of any graph with tree-width at most $k$ at any point. For a graph with $n$ vertices, the algorithm requires $O(a_k n^{2k+3})$ arithmetical operations, where $a_k$ depends only on $k$.