[Solved] CSDS455 Homework 21-tree decomposition for graph

Problem 1: Assume that you have a tree decomposition for graph G and a second graph H without a decomposition. Assume the decomposition is adjusted so that every bag has size exactly k + 1 and every bag has 0 or 2 children.

Write a dynamic programming solution to: Graph Isomorphism: Given two graphs G and H, determine if G = H.

Assume you have a tree decomposition for G but not for H. As a hint, first spend O(n^k+1) time to find all separators of size k + 1 in H. A dynamic programming solution uses a table of at most 2n^k+1(k + 1)! booleans for each bag of the decomposition.

Problem 2: Assume that you have a tree decomposition for graph G. Assume the decomposition is adjusted so that every bag has size exactly k + 1 and every bag has 0 or 2 children.

Write a dynamic programming solution to: Hamiltonian Circuit: Given a graph G, does there exist a cycle that visits each vertex of G exactly once?

A dynamic programming solution uses a table of at mostbooleans for each bag of the decomposition. S(a,b) is the Stirling number that counts the number of ways to partition a labelled elements into b non-empty, unlabelled subsets.