0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.