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

Question

We consider the problem of determining if k classes can have the 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.

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.

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.