I have the following problem.

Given a finite number of lists of items. The same item can appear in many lists. I would like to color items with 3 colors, such at least two colors appear in each list.

I would like to show that this problem is NP-hard. I would like to provide reduction from the 3-coloring problem which seems to be similar.

I think I could make items as nodes and link every item with every other from the shared lists, but then the condition of 3-coloring would be too demanding in comparison to my problem. What should I do differently in order to create the reduction?

  • 1
    $\begingroup$ Try lists of size 2. $\endgroup$ – Yuval Filmus Jun 19 '18 at 20:44
  • $\begingroup$ What do you mean? Items are not movable. $\endgroup$ – pw94 Jun 19 '18 at 21:13
  • $\begingroup$ Are you trying to reduce in the wrong direction? $\endgroup$ – Yuval Filmus Jun 19 '18 at 21:13
  • $\begingroup$ I hope I am not. I want to reduce from 3 coloring to my problem. Input to my problem are the lists of items to color. $\endgroup$ – pw94 Jun 19 '18 at 21:15
  • 1
    $\begingroup$ Given an instance of 3-coloring, you need to produce an instance of your problem. $\endgroup$ – Yuval Filmus Jun 19 '18 at 21:16

To prove that a problem is NP-hard, we need to reduce an NP-hard problem to it (which in this case as you mentioned would be 3-coloring).

So what we are trying to do, is to map every graph $G(V,E)$ to an instance of your problem, where every node $v_i$ will be mapped with an element $el(v_i)$ and every edge $\epsilon\{v_1, v_2\}$ would be represented with a two-element list $\{el(v_1), el(v_2)\}$.

So now a coloring $f:V\rightarrow C$ would be reduced to a coloring on the set of elements in your problem which means, if we found a coloring on the elements of the proposed problem, we can use the same coloring on our graph and it would be a proper coloring.

Proof. If $f:V\rightarrow C$ isn't a proper coloring, that means there is an edge with both nodes having the same color, which means there is a set with two elements and both of them have the same color which contradicts the statement of your problem.

  • 1
    $\begingroup$ Thank you very much for the answer @narek-bojikian I understand almost everything. I would like to ask about this part: "every edge would be represented with a two-element list containing the maps of nodes of the edge". The word edge appears twice and I am not sure what edge do you mean at the end of this quote. $\endgroup$ – pw94 Jun 19 '18 at 21:57
  • $\begingroup$ @pw94 i've just re-edited the explanation, hope it's clear now $\endgroup$ – narek Bojikian Jun 19 '18 at 22:54

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.