5
$\begingroup$

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:

  1. All courses are studied within 3 years: $Y_1\cup Y_2\cup Y_3=C$.
  2. 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$.
  3. 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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: use prerequisites as edges, then take the complement of the graph. $\endgroup$ – Draconis May 11 '19 at 16:31
  • $\begingroup$ Iv'e also been told that. Did not help me. Iv'e also been told to divide the courses to such that have preconditions (will match the edges) and such that don't (will match vertices). If you think you have a solution that can be correct please post it. $\endgroup$ – gusfring May 11 '19 at 16:48
  • 1
    $\begingroup$ Our reference question may help. $\endgroup$ – Raphael♦ May 12 '19 at 16:41
7
$\begingroup$

Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "edge course") in $G$. Each edge course has two precondition vertex courses corresponding to its two endpoints. In addition, we set $m_1=k,m_2=+\infty, m_3=m-\binom{k}{2}$ where $m$ is the number of edges in $G$. Now we can see there is a clique of size $k$ in $G$ if and only if it is possible to finish the degree in three years.

|cite|improve this answer
$\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.