We consider the problem of determining if k classes can have the final final scheduled at the same time. In this problem, a class C is a set (of students), so C and two classes can have the final at the same time, if they have no common student.

So the problem is SIMULTANEOUS FINAL SCHEDULING (SES) Input: Finite sets (representing students) C1, . . . , Cn and a natural number k n.

Question: Can we choose k sets from C1, . . . , Cn, so that they are pairwise disjoint (i.e., any two classes have no common element)?

(a) Show that SES is in NP. (You need to say what a certificate of a YES instance of SES is).

(b) Describe a polynomial-time reduction SES p CLIQUE.

(Notes: CLIQUE problem is described in Th 7.24 in the textbook. You need to show how to construct from an instance I1 = ((C1, . . . , Cn), k) of SES an instance I2 = (G, k0 ) of CLIQUE so that that there are k pairwise disjoint sets in if and only if G has a clique of size k 0 .)