HALF CLIQUE - NP Complete Problem Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please.  With that said, here is the problem I am looking at:


  Let HALF-CLIQUE = { $\langle G \rangle$ | $G$ is an undirected graph having a complete
  subgraph with at least $n/2$ nodes, where n is the number of nodes in $G$
  }. Show that HALF-CLIQUE is NP-complete.


Also, I know the following:


In terms of this problem a clique, is defined as an undirected subgraph of the input graph, wherein every two nodes are connected by an edge.  A $k$-clique is a clique that contains $k$ nodes.
According to our textbook, Michael Sipser's "Introduction to the Theory of Computation", pg 268, that the problem CLIQUE = {$\langle G,k\rangle$ | $G$ is an undirected graph with a $k$-clique} is in NP
Furthermore, according to the same source (on pg 283) notes that CLIQUE is in NP-Complpete (thus also obviously in NP).


I think I have the kernel of an answer here, however I could use some indication of what is wrong with it or any related points that might be relevant to an answer.  This is the general idea I have so far,


  Ok, I'd first note that a certificate would simply be a HALF-QLIQUE of $\text{size} \geq n/2$.  Now it appears that what I would need to do is to create a verifier that is a polynomial time reduction from CLIQUE (which we know is NP-Complete) to HALF-CLIQUE.  My idea would be that this would be done by creating a Turing machine which runs the turing machine verifier in the book for CLIQUE with the additional constraint for HALF-CLIQUE.


This sounds correct to me, but I don't really trust myself yet in this subject. Once again, I would like to remind everyone this is a HOMEWORK PROBLEM so please try to avoid answering the question.  Any guidance which falls short of this would be most welcome!
Judging by your description and comments, you might be helped the best by an exact description on how reductions can be used to prove NP-completeness:

A problem is NP-complete iff it is in NP and it is NP-hard. This means that any proof of NP-completeness has two parts: a proof that the problem lies in NP and a proof that it is NP-hard.

For the first part, you have to show that YES-instances can be verified in polynomial time using some suitable certificate. Alternatively, you can show the problem can be solved in polynomial time by a non-deterministic Turing machine, but this is not usually done as mistakes are easily made.

In your case, this comes down to proving that for every graph with a $n/2$-clique, you can find some proof that there is indeed such a clique, such that, armed with such a proof, you can check in polynomial time that there is indeed such a clique.

For the second part, you have to show that the problem is NP-hard. This is in nearly all cases shown by proving that your problem is at least as hard as some other NP-hard problem. If HALF-CLIQUE is as least as hard as CLIQUE, it must also be NP-hard.

You do this by proving a reduction FROM CLIQUE, TO HALF-CLIQUE. You 'reduce' the problem, making it 'easier'. You say "Solving CLIQUE is hard, but I have proven that you only need to solve HALF-CLIQUE to solve CLIQUE". (many people, even experts, occasionally say this the wrong way around :))

There are different types of reductions: the reduction that is most commonly used is the one where you map instances of in this case CLIQUE to instances of HALF-CLIQUE whose size is at most polynomially larger, in polynomial time. This means that if we can solve HALF-CLIQUE, then we can also solve CLIQUE by chaining the algorithm and the reduction.

In other words, we must show that we can solve CLIQUE if we can solve HALF-CLIQUE. We do this by showing that for every instance for CLIQUE, we can design an instance of HALF-CLIQUE such that the instance of CLIQUE is a 'yes' instance iff the instance of HALF-CLIQUE is a 'yes' instance.

The proof therefore starts like this: given a graph $G=(V, E)$, I can create some graph $H=(V&#39;, E&#39;)$ such that $G$ contains a $k$-clique iff $H$ contains a $n/2$-clique. I'll leave this part to you (this is the part that requires creativity, the part that is about the specific problem at hand).