2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Try lists of size 2. $\endgroup$
    – Yuval Filmus
    Jun 19, 2018 at 20:44
  • $\begingroup$ What do you mean? Items are not movable. $\endgroup$
    – pw94
    Jun 19, 2018 at 21:13
  • $\begingroup$ Are you trying to reduce in the wrong direction? $\endgroup$
    – Yuval Filmus
    Jun 19, 2018 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, 2018 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, 2018 at 21:16

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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, 2018 at 21:57
  • $\begingroup$ @pw94 i've just re-edited the explanation, hope it's clear now $\endgroup$
    – Narek Bojikian
    Jun 19, 2018 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.