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$?
  • $\begingroup$ A hamiltonian path (if it exists) is necessarily of size $n$ in a graph of order $n$… $\endgroup$ – Nathaniel Apr 19 at 16:25
  • $\begingroup$ 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"? $\endgroup$ – Juho Apr 19 at 18:52
  • $\begingroup$ 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$ $\endgroup$ – heretoinfinity Apr 19 at 20:36
  • $\begingroup$ 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 $\endgroup$ – D.W. Apr 20 at 2:34
  • $\begingroup$ @D.W., do you mean that each of the bullet points is actually a set of 2 questions? $\endgroup$ – heretoinfinity Apr 20 at 14:53

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.


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.