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!
Best Answer
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.