Prove NP-Completeness clique + independent set graph

"Prove that it is NP-Complete to determine given input G and k whether G has both a clique of size k and an independent set of size k. Note that this is 1 problem, not 2; the answer is yes if and only if G has both of these subsets."

We were given this problem in my algorithms course and a large group of students could not figure it out. Her开发者_JS百科e is what we have so far...

We know that both the clique and independent set problems are NP-Complete in of themselves. We also know that the verification of this problem, given some "certificate" is in NP.

The problem is somehow performing a reduction on the above problem (which contains both independent sets and cliques) to either a problem consisting entirely of cliques or independent sets (at least that's what we think we need to do). We don't know how to perform this reduction without losing information needed to reduce the reduction back to its original form.

Hint: Reduce CLIQUE to this problem, by adding some vertices.

Thanks to "Moron" and "Rafal Dowgird" for the hints! Based on that I think I've got a solution. Please correct me if I am incorrect:

Since we already know the the clique and independent-set problems are NP-Complete, we can use that as a foundation for proving our problem. Let's call our problem the Combination Clique Independent Set problem (CCIS).

Suppose we are given a graph G which has a clique C of size k. We can reduce this graph into a graph G' (read: G prime) which has both a clique C' of size k' and independent-set I of size k' by attaching k vertices to each vertex in C. This reduction occurs in polynomial time since the addition of the vertices takes O(n*k) time (n vertices in the graph and k vertices attached to each node).

Note that C=C' and k=k'.

Now suppose we are given a graph G' which has a clique C' of size k' and independent-set I of size k' which is determined to be true. The reduction to the clique problem is trivial since we don't need to modify the graph at all to find only a clique.