How much does proving that a special case of a problem is NP-complete tell me about if the general problem is NP-complete?

Question

Define a graph problem as follows. Given a graph $G$ and two integers $c$ and $k$, delete $k$ nodes and all edges incident to them, such that, in the remaining graph, every connected component has at most $c$ nodes.

What can I say about the time complexity class of the above problem? I can easily prove that under the condition that $c=1$, I can reduce Vertex Cover to the problem in polynomial time, and thereby prove that the problem is NP-hard under these parameters.

My work book says that this, accompanied with a polynomial verification, is enough to prove that the problem is NP-complete, but I have a hard time accepting this since we have only observed the problem under a certain set of parameters?

Answer 1

If a problem $P'$ is a special case of problem $P$, this means that $P'$ can be reduced to $P$. Therefore, if $P'$ is NP-hard, it follows that $P$ is NP-hard (because if any problem $H$ in NP can be reduced to $P'$, then it can also be reduced to $P$).

If you also have a proof that $P$ is in NP (your proof of polynomial verification; for $P$, not just for $P'$), then you have a proof that $P$ is NP-complete.

Answer 2

“X is NP hard” means: Any instance of any problem Y in NP can be solved by constructing and solving the right problem in X. “X is NP complete” means that in addition X is in NP.

If a subset P’ is NP complete or NP hard, then obviously P is NP hard: Just pick the same instance to solve any instance of an NP problem, not one of the added ones.

For P to be NP-complete you need to prove that P is in NP. This is never the case if P’ is not in NP.