0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

If you want a reduction from Vertex Cover: given $(G, k)$ an input of VC, create a graph $G'$ with a copy of $G$ and an additionnal $k$ vertices with no additionnal edge.

Then $G'$ has a vertex cover and an independant set of size $k$ if and only if $G$ has a vertex cover of size $k$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.