1
$\begingroup$

The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,C_2,\dots,C_k$ that you have not yet taken. There are no conflicts between courses in the same area of study, but there can be conflicts between courses in different areas of study. You have a list of $(class1, class2)$ pairs in different areas of study that are in conflict. Can you choose 1 course from each area so that there are no conflicts? Is this an NP-complete problem?

Here is what I have so far:
K-AREA-COURSE-REGISTRATION ∈ NP: Given a random list of k courses, we can check that we have one course from each area in O(k) time. We can also check for conflicts in O(k^2) time (check each pair of courses for conflict).

K-AREA-COURSE-REGISTRATION is NP-complete: Reduce 3-SAT to K-AREA-COURSE-REGISTRATION. Each 3-SAT literal becomes a course (same literal in different clause is a different course). Each clause becomes an area of study (clauses become the $C_k$ sets). Create conflicts between two courses $a,b$ if, in the original 3-SAT problem, $a=x$ and $b=\bar{x}$. Choosing one course from each set will set at least 1 literal in each 3-SAT clause true. The conflicts will stop us from setting a single literal both true and false

Question: Do I have/do you have any tips in accounting for the case of two courses $a,b$ which both map to the same literal $x$ in the original 3-SAT but are in different clauses (therefore in different $Ck$ sets). I may be able to use conflicts to make sure both $a$ and $b$ are chosen, but I was thinking I could just ignore this since all that matters in 3-SAT is at least one literal.

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Dec 1 '19 at 17:53
0
$\begingroup$

Assuming the sets $C_i$ are pairwise disjoint, this problem is very related to the independent set problem and is called maximum colored independent set (also called rainbow colored independent set). The problem goes as follows. Given a graph and a colouring function over the vertices of the graph. Find a maximum independent set with each vertex in the set having a different colour. The problem is NP-hard as well (try to reduce Independent set).

Assuming the sets are not disjoint the problem does not get easier since the version with disjoint sets is only a special case of this problem.

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