CSDS 455: Applied Graph Theory
Homework 21
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 most Pb
k+1
2
c
s=1
k+1
2s
S(2s, 2)2k+1−2s booleans 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
