# CS 163/265, Fall 2022, Homework 6

Due Friday, November 18, in Gradescope.

1. The graph below is an example of a series-parallel graph (from the Wednesday, Week 7, notes on treewidth). Explain why the treewidth of this graph must be at least 2. (Hint: what can we say about the cliques in this graph?)

2. For the graph in Question 1:

1. This graph has minimal separators for the vertices $$a$$ and $$h$$ that are not cliques. Find such a separator.

2. Draw or list a set of additional edges that give a minimal chordal completion of this graph.

3. The figure below shows a path decomposition of the graph in Question 1.

1. Both classes: Suppose we run the fixed-parameter tractable coloring algorithm from the lecture notes on treewidth, using two colors: R and B. Consider the bag labeled "abe". Explain why, under the definition of "good" given in the algorithm, the following coloring is not good for this bag: $$a$$: R, $$b$$: B, $$e$$: R.

2. 265 students only: Describe a simpler algorithm for optimally coloring this particular graph. (Hint: is the graph 2-colorable? If so, what does this imply?)

4. The fixed-parameter tractable clique-finding algorithm from the slides uses the fact that every maximum clique in a graph is contained entirely in at least one bag of any tree (or path) decomposition for that graph.

1. 163 students only: Is this also true for maximal cliques that are not maximum? Why or why not?

2. 265 students only: Prove that this is true for tree decompositions. (Hint: we argued this for path decompositions in the lecture slides, using the two defining rules of a path decomposition. Generalize this reasoning.)