从顶点盖减少到独立集问题

Question

假设存在某种算法，该算法以$ n $为$ n $的时间多项式解决顶点覆盖问题，而$ k $的指数为$ k $，看起来像$ o（k^2 55^kn^3）$。我们可以声称，独立集也可以在$ n $和$ k $方面的及时多项式解决吗？ （这里的$ k $代表独立集的最小尺寸）

Answer 1

否。带有尺寸$ k $的顶点盖的图形具有独立的尺寸$ nk $，因此我们不再有$ n $限制在多项式部分。

这种分离是参数化复杂性的基本猜想之一。参数化的复杂性是一种双变量复杂性理论，其中不仅给正常输入，而且给出参数。例如，（自然）参数化版本的顶点封面是：

顶点盖
输入: ：图$ g $，一个正整数$ k $。
范围: ：$ k $。
问题: ：$ g $最多有$ k $的顶点盖？

因此，每个参数化问题都有两个（正式的）指标：输入$ n $的大小和参数$ k $。然后我们说一个问题$ pi $是 固定参数可进行 如果有一种算法决定每个实例$（x，k）$ pi $的$ pi $，以$ f（k） cdot cdot | x | x |^{o（1）} $用于某些可计算函数$ f $仅取决于$ k $（即$ | x | = n $的多项式，但在$ k $中基本上是免费的）。我们称所有此类问题的课程$ fpt $。

因此，当通过顶点盖的大小进行参数化时，顶点盖为$ fpt $。

参数化复杂性的主要棘手性框架称为$ W $ hierArchy，一系列类$ w [t] $，其中$ w [i] subseteq w [i+1] $和$ fpt subseteq w [1] $。尽管它分为很多课程，但$ w $ hierachy与$ fpt $的实用关系类似于$ np $ to $ p $，如果问题为$ w [t] $ - 对于一些$ t $来说，很难，然后除非$ w [t] = fpt $，否则它没有$ fpt $算法，并且我们认为$ fpt subset w [1] $的原因与$ p subset np $。

最后，回到您的问题，最后，事实证明，当通过独立集的大小进行参数化时，独立集为$ W [1] $ - 完成。也就是说，除非$ w [1] = fpt $，否则独立套件没有算法的运行时间，以$ f（k）n^{o（1）} $限制任何$ f $，其中$ k $是大小独立集。

附加说明:

当然，我们不必以答案的大小来参数化，我们可以使用任何感觉，正常的准则是，与输入大小相比，它应该是合理地期望很小的东西，并且应该应该能够独立于输入大小而变化。例如，一个常见的结构参数是图的树宽。您可以通过与输入大小有关的测量进行参数化，但是我们必须引入许多不同的类。