In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $c$ such that $c(v) \in L(v)$ for all $v \in V$ and $c(i) \neq c(j)$ for all $<i,j> \in E$. If such a coloring exists, we say that $G$ is $L$-colorable and that $c$ is an $L$-coloring of $G$.

In my problem: Given a graph $G(V,E)$ an integer $k$, for tractability, we take over the coloring using natural number from 1 to k. Each vertex is required to be colored by an exact number, and each vertex has different weights corresponding to its permissible colors (numbers). The objective is to minimize the sum of the weights of $v \in V$ while satisfying no any two adjacent vertices are colored using same number.

I want to prove the above problem (called P1) is $\mathcal{NP}$-complete.

Answer: Reduce the $L$-coloring List Coloring Problem to P1.

I now define a decision version problem (called P2): Given an undirected graph $G(V,E)$ and an integer $k$ in the List Coloring Problem, we ask whether a $k$-coloring can be found in $G$.

In my opinion, to solve P1, we have to solve P2 firstly and then find the minimum sum from the feasible solutions set. Since LCP is a generalization of graph coloring problem(GCP), i.e., the latter is a special case of the former, and it is well known that the $k$-coloring problem in GCP is $\mathcal{NP}$-complete. Thus, we can say that the $k$-coloring problem in LCP is also $\mathcal{NP}$-complete, i.e., P2 is $\mathcal{NP}$-complete. This concludes that P1 is also $\mathcal{NP}$-complete. Is this reduction correct?

I would sincerely appreciate if someone can give any useful suggestions!

  • $\begingroup$ the question is not clear can you please be more specific about the question? (Do you want a reduction from P1 to list coloring problem or you are just asking if such a reduction suffices for the proof) $\endgroup$ – narek Bojikian Oct 25 '19 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.