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