# Are problems that are fractions of constraints of NP-complete problems also NP-complete?

We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $$n$$ ? That is, for a graph, $$G$$ of $$n$$ nodes,

• is there a Hamiltonian path of size $$\frac{n}{2}$$ or of $$\sqrt{n}$$ or any number of nodes less than $$n$$?
• is there an independent set of size $$b$$ in $$\frac{n}{2}$$ or of $$\sqrt{n}$$ or any number of nodes less than $$n$$?
• is there a clique of size $$k$$ in $$\frac{n}{2}$$ or of $$\sqrt{n}$$ or any number of nodes less than $$n$$?
• A hamiltonian path (if it exists) is necessarily of size $n$ in a graph of order $n$… – Nathaniel Apr 19 at 16:25
• I don't understand the problem statements. For example, what's the intended difference between the second problem and "is there an independent set of size b on a given graph"? – Juho Apr 19 at 18:52
• Instead of an independent set with $G$ of size $n$, finding an independent set of a subgraph, $G'$, of $\frac{n}{2}$ nodes that are from $G$ – heretoinfinity Apr 19 at 20:36
• It looks like you're asking about 6 different questions here. There is no reason that the answer will necessarily be the same for all of them. The usual rule is to ask only one question per post – D.W. Apr 20 at 2:34
• @D.W., do you mean that each of the bullet points is actually a set of 2 questions? – heretoinfinity Apr 20 at 14:53

## 1 Answer

There is no general rule that they necessarily need to be NP-complete in general.

For the specific examples you list, I expect the answer will be that each of those specific examples are NP-complete, but I haven't tried to prove or verify that; that's just speculation.