In order to show that the next problem is NP-hard:
Problem: Vertex Cover and Independent Set
Input: Graph G and integer k
Output: Does G have a vertex cover of k and an independent set of k?
The sets does not have to be complementary (just about size k). I have tried to reduce Vertex Cover but I cannot find how to ensure that when there is a vertex cover in G, the problem above outputs true and deal with the independent set of the same size k. I have thought of doing something with the fact that vertex cover is the complement of independent set but since there is the same value for k I have no idea for that.