通过顶点盖解决独立集

Question

我有一个独立的设置问题，其中我必须检查给定图形是否具有给定尺寸 $ k $ 。我已经写了一个顶点封面算法一边，我希望我能在这里重复使用它。这些算法密切相关，因为如果图 $ g=（v，e）$ 具有大小 $ k $ IFF它具有大小的VC $ v - k $ 。所以我是我可以使用我的VC算法与 $ k'= v - k $ ？

我读到了这个和这个问题和之后我开始怀疑这是简单的。

Answer 1

这是简单的，那些问题正在谈论固定参数易行算法w.r.t.尺寸 $ k $ 的独立设置/顶点封面。您的算法将只能正常设置 $ k'= | v | - k $ 。显然，新值 $ k'$ 也影响算法的运行时间。