I was asked in an interview the following question:
We'll define the "Finishing the degree in three years" problem in the following manner:
Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, where every course $c_i\in C$ is given a list $R_i\subseteq C$ of the precondition courses for this course, and also we are given the maximal amount of courses in each year $m_1, m_2, m_3$, and we need to decide if it is possible to finish the degree in three years. Meaning, can we divide the courses for three years $Y_1, Y_2, Y_3 \subseteq C$, such that the following conditions are satisfied:
- All courses are studied within 3 years: $Y_1\cup Y_2\cup Y_3=C$.
- Each courses is studied only after all of its precondition courses have been studied, meaning: for any $c_i\in Y_1: R_i\subseteq\emptyset$, for any $c_i\in Y_2: R_i\subseteq Y_1$, for any $c_i\in Y_3: R_i\subseteq Y_1\cup Y_2$.
- The number of courses studied in each year is not higher than maximum allowed, meaning: $|Y_i|\le m_i$ for each $i\in\{1,2,3\}$.
Prove that the "Finishing the degree in three years" problem is NP-Complete.
I was told that the reduction should be from the clique problem but it has been a week since I've started thinking about it and I couldn't prove it. If someone can please post a thorough solution I would appreciate it a lot.