I have an NP hard problem $P$ that takes in arbitrary $G = (V, E)$ as input. I have another problem $Q$ that I want to show is NP hard, and this problem has arbitrary complete graphs $G'$ as input. Is this enough to say that $Q$ is also NP hard, since it is a subclass of the NP-hard problem with arbitrary inputs, or is this insufficient?
1 Answer
$\begingroup$
$\endgroup$
It is not sufficient, an "input restriction" like that can easily move that problem to a lower complexity class.
For example, graph coloring in general is NP hard, graph coloring on only complete graphs is trivial.
