========================================================================
CSC 363H                 Tutorial Exercises #11              Summer 2007
========================================================================

CLIQUE(G,k): Does graph G have a clique of size k?
HALF-CLIQUE(H): Does graph H have a clique of size h, where h is half 
                the number of nodes in the graph?

We show that HALF-CLIQUE is NP-Complete by reducing CLIQUE to it.

Suppose we are asked whether CLIQUE(G,k), and let n denote the number of 
nodes in the graph G.  Then we will construct a new graph H such that 
CLIQUE(G,k) iff HALF-CLIQUE(H).

There are three possible cases for the relationship between k and n/2:

Case 1: k = n/2
---------------
Then just let H = G.

Case 2: k < n/2
---------------
Then the basic idea is to add totally connected nodes to the graph, 
boosting the size of any k-clique so that it will equal half the size of 
the new graph.

In particular, H = G with n-2k new nodes.  All the new nodes are connected 
to each other, as well as to every node in G.

Case 3: k > n/2
---------------
Then the basic idea is to add a bunch of junk nodes to pad the total 
number of the nodes of the graph, while making sure that we are not 
upgrading any cliques.

In particular, H = G with 2k - n new nodes.  The first new node is 
connected to an arbitrary node in G, and the second new node is connected 
to the first.  The third new node is connected to the second, and so on, 
creating a "chain" or a "tail."

For each of the three cases, we now just need to verify that CLIQUE(G,k) 
iff HALF-CLIQUE(H).