I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a complete graph that solves B.

Since undirected graphs generalize complete graphs, am I safe in saying that A is NP-Hard for undirected graphs? Something about that doesn't seem right to me, since problem A on complete graphs is essentially the "non-graphical" version of the problem. Am I missing something?

Disclaimer: I am new to proving hardness results.

  • 1
    $\begingroup$ You aren’t missing anything. $\endgroup$ – Yuval Filmus Nov 16 '18 at 0:38

Usually, when reducing problem B to problem A, not all possible instances of problem A appear in the image of the reduction. This is absolutely not an issue.

In your case, you can say that problem A is NP-hard even if restricted only to complete graphs. This is a stronger result, which is a good thing, and definitely allowed.

As an example, 3-coloring is hard even for 4-colorable graphs, and even just for planar graphs. You show this (say) by reduction from SAT to 3-coloring, in which all the resulting graphs are planar. This is not a drawback – in fact it's a bonus.

| cite | improve this answer | |

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.