# Proving NP-completeness for a problem is a generalization of a known NP-complete problem

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!

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.
• 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. – Wei Jun 24 at 2:37