We consider the problem of determining if k classes can have the final final sch

Question

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

Explanation / Answer

K classes -final scheduled at same time
C class-Set of students and two class have the final at the same time
Solution
First, we must show that SES NP by showing that a solution can be verified in polynomial
time. We first verify that | C |= k. Then, we verify
for each students form the class C C1 K,C2 K.....Cn K and choose two students from class Cn and K who make a disjoint pair.
time. Thus, the solution can be verified in polynomial time, and IS NP.

Second, we must show that SES NP by showing that a known NP-Complete problem
reduces to SES; namely, we show that SES P CLIQUE , i.e., there is a polynomial-time
reduction f of any CLIQUE problem to an SES problem such that C1,C2..Cn CLIQUE if
and only if K IS. The class K form an independent set of students with class c. Therefore, the NP-Complete CLIQUE problem is poly-time
reducible to SES.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.