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?)

    a series-parallel graph, with vertices a,b,c,d,e,f, and edges (a, b), (b, c), (b, d), (b, f), (a, g), (c, e), (d, e), (f, e), (e, h), and (g, h).

  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.

    a path decomposition with bags (from left to right) cbe, bde, bfe, abe, age, aeh.

    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.)