This thesis investigates the computational complexity of algorithmic problems defined on graphs. At the abstract level of the complexity spectrum we discriminate polynomial-time solvable problems from NP-complete problems, while at the concrete level we improve on polynomial-time algorithms for generally hard problems restricted to tree-decomposable graphs.
One contribution of this thesis is a precise characterization of vertex partitioning problems which include variants of domination, coloring and packing. An elaboration of this characterization is given for problems defined over vertex subsets and over maximal/minimal vertex subsets. We introduce several new graph parameters as vertex partition generalizations of classical parameters. The given characterizations provide a basis for a taxonomy of vertex partitioning problems, facilitating their common algorithmic treatment and allowing for their uniform complexity classification.
We explore the computational complexity of two important types of problems within this taxonomy: vertex subset optimization problems and H-covering problems. The taxonomy is particularly useful in categorizing and analyzing the complexity of vertex subset problems, of which there are a great variety. Our investigation of the complexity of vertex subset problems uncovers several infinite classes of NP-complete and of polynomial-time solvable problems. These results are contrasted and compared with the complexity of classical vertex subset problems. We also develop a methodology useful in analyzing the complexity of H-covering, a problem parameterized by a fixed graph H. As an illustration, we settle the complexity of the H-covering problem for any simple graph H on at most 6 vertices. We design efficient algorithms for H-covering problems by reduction to the 2-SAT problem and by reduction to factorization problems in regular graphs.
Another contribution of this thesis is a methodology for the design of practical algorithms for generally NP-hard problems restricted to partial k-trees. Based on very simple graph operations, we define a binary parse tree of partial k-trees that facilitates algorithm derivation. We account for dependency on the treewidth k in analysis of the computational complexity of the resulting algorithms.
These contributions culminate in applying the partial k-tree algorithm methodology to the general class of vertex partitioning problems. The input graph in the resulting algorithms is assumed to be given with a width k tree-decomposition, and the answer is computed by a dynamic programming bottom-up traversal of its binary parse tree. We give the first algorithms for these problems with reasonable time complexity as a function of treewidth. We also give the first polynomial-time algorithms on partial k-trees for certain problems, mainly Grundy Number, not known to have a finite state description even if restricted to graphs of bounded treewidth.