Given a list of $N$ courses, $M$ students, the list of courses each student is taking and an integer $K$ representing the duration of the exam phase, is there an exam schedule consisting of $K$ dates so that there are no conflicts? Can you show that this problem is as difficult as the Clique-Cover problem (is $NP$-complete)?
$\begingroup$
$\endgroup$
-
$\begingroup$ If $K>N$ the problem is easy. $\endgroup$ – Henrik supports the community Dec 27 '14 at 17:31
-
$\begingroup$ Hint: Consider the graph with a vertex for each course and an edge between two courses if they have a student in common. Is it $K$-colorable? (If you want to reduce from clique cover instead, put edges between courses with disjoint sets of students). $\endgroup$ – hmakholm left over Monica Dec 27 '14 at 18:35
$\begingroup$
$\endgroup$
Let the courses be vertices. Draw an edge between two if those courses have no student in common, i.e. their exams may be scheduled concurrently. If there happens to be a $3$-clique, then all $3$ of those courses may have their exams at the same time.
