1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I just reword, is it better now? $\endgroup$ – Wei Jun 23 at 20:09
  • $\begingroup$ Yes, thank you. $\endgroup$ – Henning Makholm Jun 23 at 20:12
1
$\begingroup$

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

  • connecting each of the new vertices to every other new vertex that will get a different color, and
  • giving color $n$ a capacity of $nv+v-1$ for $n=1,2,\ldots,k$.

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.

$\endgroup$
  • $\begingroup$ @Wei: Well, solving your problem requires also solving the decision problem of whether a solution that meets the constraints exists at all, doesn't it? $\endgroup$ – Henning Makholm Jun 23 at 21:05
  • $\begingroup$ I think so. I think a lot and try to prove that the sum of color numbers is minimized iff a k-colorable in LCP is solvable. $\endgroup$ – Wei Jun 23 at 21:15
  • $\begingroup$ @Wei: Then you don't need to care about the fact that your problem would also minimize something! Just ask, "does this instance of the problem have a solution with sum less than $k^2v^2$?" $\endgroup$ – Henning Makholm Jun 23 at 21:17
  • $\begingroup$ But I am still confused how to make this convinced: the sum of color numbers is minimized iff a LCP is k-colorable? Thanks again! $\endgroup$ – Wei Jun 23 at 21:21
  • $\begingroup$ @Wei: When you're reducing TO your problem you're the one who decides what the particular instance of your problem you construct will look like. Nobody says you have to use everything it can do! (It would be different if you're solving your problem, but that's not what you're doing here. When you're reducing TO the problem, you imagine that someone else has constructed a machine for your problem, and you're then imagining what you can do with that machine. You don't need to press all of the buttons if there are a few of the buttons that can do the thing you want!) $\endgroup$ – Henning Makholm Jun 23 at 21:23

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.