Draft Solutions for 611 Final 2009
Question 1:
1) At each step, pick any node, put it into your independent set, and remove it and its neighbors. Continue until there are no nodes remaining. Every time you removed a node and its neighbors you removed at most d+1 nodes. Hence, you must have repeated the process \geq ceiling(n/(d+1)) times. Since the maximum independent set includes at most n nodes, your algorithms gives a d+1 approximation.
2) Consider the above algorithm but always picking leaf nodes. Argue why this is optimal.
Question 2:
Need to show that CLIQUE COVER is in NP and that GRAPH COLORING \leq_P CLIQUE COVER. For the first part, it suffices for the certificate to be k disjoint sets with the required property. For the second part consider taking an instance of GRAPH COLORING where you are asked with it is possible to color a graph G is k colors. Transform G to G' be replacing edges with non-edges and vice versa. Argue that CLIQUE COVER on G' with parameter k is true iff GRAPH COLORING on G with parameter k is true.
Question 3:
Define A[j]=1 if s[1...j] can be reconstituted from valid works and 0 otherwise.
Then A[j]= 1 iff there exists i