# Solving Independent Set through Vertex Cover

I have an Independent Set problem, in which I have to check if given graph has a IS of given size $$k$$. I've already written a Vertex Cover algorithm a while back and I hope I can reuse it here. Those algorithms are closely related, since if graph $$G = (V, E)$$ has IS of size $$k$$ iff it has VC of size $$V - k$$. So am I right that I can I just use my VC algorithm with $$k' = V - k$$?

I've read this and this question and after that I've started doubting that this is that simple.

• Seems like you have answered yourself... Commented May 5, 2020 at 13:37
• @Steven I've read cs.stackexchange.com/questions/11904/… and cs.stackexchange.com/questions/87067/… and after that I've started doubting that this is that simple. Commented May 5, 2020 at 13:39
• @Steven thank you, I just got confused here! Please post an answer, I'll accept it right away. Commented May 5, 2020 at 13:45
• I took the liberty to edit your question to add a bit of context, since simple yes/no questions are discouraged. Commented May 5, 2020 at 13:49

It is that simple, those questions are talking about fixed parameter tractable algorithms w.r.t. the size $$k$$ of an independent set/vertex cover. Your algorithm will work just fine setting $$k' = |V| - k$$. Clearly, the new value $$k'$$ also affects the running time of your algorithm.