1
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

“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.

$\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.