Prove NP-Completeness clique + independent set graph

Question

"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. Here 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.

Truax

See also Question about NP-Completeness of the Independent Set Problem. – Berbera

Answer 1

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

Fulsome

Alternatively: reduce INDEPENDENT-SET to this problem by adding some vertices and edges. – Mcneal

Answer 2

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.

Truax

An easier reduction from Clique to CCIS is to take your input graph for Clique and add k isolated vertices to it. (Strictly speaking, if k is presented in the input in binary, adding k extra vertices is an exponential amount of work relative to the length of the input. So you should check that k is at most the number of vertices in the graph: if k is greater than that, produce any small "no" instance, e.g., the graph on a single vertex.) – Yellowhammer