Show basic scheduling problem is NP Complete

Question

Suppose you have a list of S students, a list of C classes and a list of which modules each student takes. I want to schedule every class during a 5 day exam period.

Constraints: Their are only 2 exam slots per day. If there is a pair of modules where one or more students are taking both modules, we cannot schedule their exams at the same time.

My attempt: To show something is NP Complete, must show it is in NP and a reduction of an NP Hard Problem. Clearly, it is in NP because given a certificate of a scheduling, you can just check there are no conflicts.

I want to show this is a reduction of either SAT or Graph Coloring. I'm not sure exactly how to go about that.

Answer 1

Consider the decision problem, "Given set of students $S$, set of courses $C$, and $k$ time slots ($10$ in our case), is there an assignment of courses to slots such that no student has a scheduling conflict?"

NP-completeness for $k \geq 3$ can be proved by reduction from $k$-coloring, which is known to be NP-complete for $k \geq 3$ (Karp, 1972; [GT4] in Garey and Johnson).

Given an instance of $k$-coloring, map every color to a slot, every vertex to a course, and every edge to a student who is enrolled in both courses corresponding to the endpoints of the edge.

The reduction is clearly polynomial and membership in NP is obvious, as you note. Since Karp originally proved NP-completeness of $k$-coloring by reduction from 3SAT, it is clearly possible to do the same in this case, but reduction from $k$-coloring is so straightforward...