I am trying to solve a problem that can be considered as minimizing the sum of colored numbers in a List Coloring Problem while satisfying some restricted constraints.
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: 1) a graph $G(V,E)$; 2) an integer $k$, for tractability, we use a natural number from 1 to k (i.e., the total number of colors is $k$) to represent a color one by one. We assume that each color has a specific capacity, i.e., how many times it can be used at most in $G$, and each vertex must be assigned by an exact number. The objective is to minimize the sum of color numbers of $v \in V$ while satisfying no any two adjacent vertices are assigned same number and the color capacity is not violated.
I want to prove the above problem is $\mathcal{NP}$-complete.
The only possible reduction I can come up with seemingly is to reduce the $L$-colorable List Coloring Problem to my problem. It is well known $k$-colorable in graph coloring problem is $\mathcal{NP}$-complete and the List Coloring Problem is a generalization of graph coloring problem, can I say the $k$-coloring in List Coloring Problem is also $\mathcal{NP}$-complete?
Moreover, I am not very sure whether a problem is still $\mathcal{NP}$-complete after adding capacity constraints.
I in advance appreciate if someone can give any useful suggestions!
Best Answer
The challenge here is not that your problem has "added capacity constraints" -- that just gives you a richer language of instances, and you can just chose not to use that possibility when you generate instances of your problem as part of the reduction. But it is a challenge that your problem doesn't have the explicit color list constraints, because you need to find a way to handle input instances that do have nontrivial list constraints.
In order to reduce LCP to your problem, you must show how to take an LCP instance and -- in polynomial time -- produce an instance of your problem that has the same answer.
Suppose the LCP instance has $v$ vertices and $k$ colors. Without loss of generality I'll assume there's at least one edge, too, such that the vertices can't all have the same color.
Now, suppose we add $v$ new vertices that we will force to have color $1$, and $2v$ new vertices that we will force to have color $2$, and so forth up to $kv$ new vertices that will be forced to have color $k$. This "forcing" can happen by
Now the only way to satisfy the capacities is by giving each new vertex the desired color. We can then enforce the color lists by adding edges between each old vertex and new vertices of the colors that old vertex must not have.
This gives you an instance of your problem that is solvable iff the original LCP instance was.