Reference no: EM132122233

Remember all of the following steps when showing that a problem D is NPcomplete:

1. Show that D is in NP by briefly explaining how to quickly verify a solution to it.

2. Choose another problem Q that is known to be NP-hard (one that we showed in class) and explain how you convert an instance of that problem into an instance of D (this is to show that D is NP-hard).

3. Explain why a yes-instance of Q gets turned into a yes-instance of D.

4. Explain why a no-instance of Q gets turned into a no-instance of D.

Consider the following problem: the input is a list of final tests F1...Fk that need to be scheduled, a list of students S1...Sm each of whom needs to take a certain subset of tests, and a number t which is the number of scheduling timeslots available to put tests in (multiple tests can happen at the same time).

The input is a yes-instance of SCHEDULE if there is a way to assign each test to one of the t timeslots such that no student would have to take two tests at the same time. For example, given the input t = 2, S1 = (F1, F2); S2 = (F1, F3); S3 = (F2); S4 = (F2, F4), this is a yes-instance, since if we schedule F1 and F4 in the first timeslot, and F2 and F3 in the second timeslot, no student has two tests that share the same timeslot.

Prove that this problem is NP-complete (Hint: reduce from 3-COLOR.

In this scheduling problem, we have the restriction that no student can have two tests in the same timeslot. What aspect of coloring a graph is this similar to?)