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<j such that A[i]=1 and dict(s[i+1 ... j])=true

Compute the values of A[j] in increase order of j and return A[n]. There are n values to compute and each takes O(n) time hence total running time is O(n^2).

Question 4:
Should be straight forward from notes/slides.

Question 5: 
1) Very similar to a question in the last homework. Expected value is 7m/8.
2) Expected number of clauses not satisfied is m/8. For less than 5m/8 of the clauses to be satisfied, then the number of not satisfied clauses must be greater than 3m/8. Hence, by Markov we conclude that this happens with probability at most 1/3.
3) Since each clause is now independent and each is satisfied with probability 7/8, the probability they are all satisfied is (7/8)^m