Dynamic Programming on Graphs with Bounded Treewidth

In this paper we study the complexity of graph decision problems, restricted to the class of graphs with treewidth ≤k, (or equivalently, the class of partial k-trees), for fixed k. We introduce two classes of graph decision problems, LCC and ECC, and subclasses C-LCC, and C-ECC. We show that each problem in LCC (or C-LCC) is solvable in polynomial (O(n C )) time, when restricted to graphs with fixed upper bounds on the treewidth and degree; and that each problem in ECC (or C-ECC) is solvable in polynomial (O(n C )) time, when restricted to graphs with a fixed upper bound on the treewidth (with given corresponding tree-decomposition). Also, problems in C-LCC and C-ECC are solvable in polynomial time for graphs with a logarithmic treewidth, and in the case of C-LCC-problems, a fixed upper bound on the degree of the graph.
Also, we show for a large number of graph decision problems, their membership in LCC, ECC, C-LCC and/or C-ECC, thus showing the existence of O(n C ) or polynomial algorithms for these problems, restricted to the graphs with bounded treewidth (and bounded degree). In several cases, C=1, hence our method gives in these cases linear algorithms.
For several NP-complete problems, and subclasses of the graphs with bounded treewidth, polynomial algorithms have been obtained. In a certain sense, the results in this paper unify these results.