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(nk+1) time to find all separators of size k + 1 in H. A dynamic programming solution uses a table of at most 2nk+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 most booleans for each bag of the decomposition. S(a,b) is the Stirling number that
