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.

  • $\begingroup$ Firstly this problem definitely is not NP-complete since it is not a decision problem. Secondly please clarify what is an exam slot. Are there multiple exams in parallel? Can one student take two modules in one day? $\endgroup$ – Smylic May 17 '17 at 14:59

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.