0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Seems like you have answered yourself... $\endgroup$
    – Steven
    Commented May 5, 2020 at 13:37
  • $\begingroup$ @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. $\endgroup$
    – qalis
    Commented May 5, 2020 at 13:39
  • $\begingroup$ @Steven thank you, I just got confused here! Please post an answer, I'll accept it right away. $\endgroup$
    – qalis
    Commented May 5, 2020 at 13:45
  • 1
    $\begingroup$ I took the liberty to edit your question to add a bit of context, since simple yes/no questions are discouraged. $\endgroup$
    – Steven
    Commented May 5, 2020 at 13:49

1 Answer 1

Reset to default
1
$\begingroup$

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.

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.