Prove the clique of NP-completeness + independent graph of the set

Question

"Prove that NP-Complete determines the given input G and k, whether G has both a clique of size k and an independent set of sizes 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 algorithm, and a large group of students could not understand it. Here is what we have so far ...

We know that both the clique and the independent tasks of the NP-Complete set are on their own. We also know that checking for this problem, given some "certificate", is in NP.

The problem is to somehow reduce the problem on the aforementioned problem (which contains both independent sets and cliques) or to a problem consisting solely of cliques or independent sets (at least what we consider necessary). We do not know how to carry out this reduction without losing the information necessary to reduce the reduction to its original form.

Answer 1

Tip. Reduce the CLIQUE to this problem by adding a few vertices.

Answer 2

Thanks to Moron and Rafal Dowgird for the tips! Based on this, I think I have a solution. Please correct me if I am wrong:

Since we already know that cliques and problems with the independent set NP-Complete, we can use this as a basis for proving our problem. Let us talk about our issue, “The Challenge of Independent Build Clique Clique” (CCIS).

Suppose we are given a graph G that has a clique C of size k. We can reduce this graph to a graph G '(read: G prime), which has both a clique C' of size k 'and an independent set I of size k', attaching k vertices to each vertex in C. This reduction occurs in polynomial time , since adding 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 an independent set I of size k', which is defined as true. The reduction to the click problem is trivial, since we do not need to change the schedule at all to find only the click.