Solving Independent Set through Vertex Cover
-
29-09-2020 - |
Question
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.
Solution
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.