Md Kamruzzaman

• Many graph counting problems are NP-hard but can be solved in linear or polynomial time with a dynamic programming algorithm when we restrict the input graph with bounded treewidth or pathwidth. We introduce the concepts of tree decomposition and path decomposition and convert them into a nice tree decomposition and a nice path decomposition, respectively, which are more convenient for our problem. We consider a graph G with n vertices with treewidth or pathwidth at most k (partial k-tree) and solve vertex partitioning problems such as counting the total number of independent sets, connected spanning subgraphs, connected induced subgraphs, and vertex colorings of j colors. We describe the general framework of a fixed parameter (k) tractable algorithm that solves all the mentioned counting problems and analyzes its complexity. This means that for a fixed treewidth or pathwidth k, the time complexity of the algorithm is polynomial in the number of vertices n, though it might be exponential in k.