4
$\begingroup$

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)?

$\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
0
$\begingroup$

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.

$\endgroup$

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.