[For the entire collection see Zbl 0639.00042.]
We study the complexity of graph decision problems, restricted to the class of graphs with treewidth \(\leq 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 logarithmic treewidth, and in the case of C-LCC-problems, with 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.