2
$\begingroup$

For example, the List Coloring Problem (LCP) is a generalization of Graph Coloring Problem (GCP). As known, given graph $G(V,E)$ and an integer $k \leq |V|$, the question that whether $G$ is $k$-colorable in GCP is $\mathcal{NP}$-complete.

Since LCP is a generalization of GCP, can I say the decision question that whether $G$ is $k$-colorable in LCP is also $\mathcal{NP}$-complete? Is it necessary to prove by strict reduction?

Thanks a lot if someone can give any answers!

$\endgroup$
2
$\begingroup$

What does it mean for one problem to be a generalization of another? It means that there is an easy reduction from the latter to the former.

In your case, LCP is a generalization of GCP, and so there should be an easy reduction from GCP to LCP: Given an instance $(G,k)$ of GCP, construct an instance of LCP by taking $G$ and giving each vertex the list $\{1,\ldots,k\}$. The new problem is completely equivalent to the original one. This is a polytime reduction, and so since GCP is NP-hard, so is LCP.

In order to show that LCP is actually NP-complete, you need to show that it is in NP. Here the reduction is of no help, and you have to prove it directly. But this is easy – the witness is a valid list coloring, which is easily checkable in polynomial time.

$\endgroup$
  • $\begingroup$ Thanks again! But what if the LCP is restricted by some constraint such as each color has a capacity, i.e., the maximum number of times it can be used in $G$. Do I necessarily to prove this problem considering the capacity? Or ignore the capacity constraint during the reduction procedure. $\endgroup$ – Wei Jun 24 at 2:37
  • $\begingroup$ In order to show that a problem is NP-hard, you have to reduce another NP-hard problem to it. Nothing more, nothing less. $\endgroup$ – Yuval Filmus Jun 24 at 3:07
  • $\begingroup$ So, does it mean that I have to reduce another NP-hard problem which includes corresponding capacity constraint to my problem? $\endgroup$ – Wei Jun 24 at 3:17
  • $\begingroup$ In order to show that a problem is NP-hard, you have to reduce another NP-hard problem to it. Nothing more, nothing less. You work out what it implies in your case. $\endgroup$ – Yuval Filmus Jun 24 at 3:18
  • $\begingroup$ I am still confused. Can you explain more specifically? In my case, the color capacity is considered in LCP, but not in GCP. I don’t know if it will make any difference in reduction. $\endgroup$ – Wei Jun 24 at 3:30

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.