顶点封面问题修改

Question

修改顶点覆盖问题。
给定图G，G是否具有10个顶点的顶点盖？这个问题还在NP中吗？
给定图G和整数K，G是否具有带有K顶点的顶点盖？
这两个问题是否有重要区别？

Answer 1

对于固定的$ c $（即，我们认为$ c $是常数），这在时间$ n^cm $中是可行的，这是$ n $中的多项式，但是，如果$ k $是输入的一部分，则是$ n^k $将被视为$ k $中的指数。

顶点盖可在$ 2^k cdot n^{o（1）} $中解决。