Half Clique Problem with examples ( Complexity theory )

Half-clique problem is described as follows. Given a graph G with n number of vertices, does there exist a clique of G consisting of exactly  half the nodes of G? Show that HALF-CLIQUE is NP-hard by reducing CLIQUE to  HALF-CLIQUE.

 Let f be a transducer which does the reduction.

f(G,k) =  Construct G' as follows
              Add n more vertices to G.
              Select n-k of the newly added vertices, connect them to each other and to all  original vertices in G.
             
Output (G')

Here adding n-k vertices to G can be done in polynomial time. So reduction is done in polynomial time.
Yes Instance

In the following example G has 5 nodes. Let k=3. This is a yes instance since G has a clique of k=3( nodes A,B and E).

Construct G' by adding 5 more nodes (F,G,H,I,J)  to graph G. Connect 5-3=2 of them to each other and to original nodes of G.

G' has five-clique (A,B,E,F and G). 
G' will not have 5-clique unless G already has a 3 clique.

No Instance

Try yourself.:

Remove any of the edges forming 3 clique and try to construct G'. Check whether G' can have a 5-clique.


Clique can be reduced to any fractionof clique using the same logic. To solve (1/m)th clique, add (m-1)n vertices to graph G and connect n-k vertices.
For example, to solve quarter-clique, add 3n vertices to G and fully connect n-k new vertices.