1

如果P不等于，NP是否可以证明k在最优顶点覆盖范围内没有近似算法，k固定常数在哪里？

4

1 回答 1

0

如果要根据附加误差来理解问题，则不存在这样的算法。针对一个矛盾，假设A是这样一个算法；这意味着存在一个非负整数k，使得对于任何图G，

A(G) <= tau(G) + k

成立，其中A(G)是由G生成的顶点覆盖的基数，A并且tau(G)表示最小顶点覆盖的基数。k考虑到上述算法的存在，让我们选择最小。特别是，我们有k => 1，否则顶点覆盖问题可以在多项式时间内解决，除非P=NP成立，否则这是不可能的。

设G为任意图；G'通过获取 的k+1同构副本来创建图形G；然后

tau(G') = (k + 1) tau(G)

持有。此外，我们得到以下内容。

A(G') <= tau(G) + k
       = (k + 1) tau(G) + k

让G*是 in 的同构副本，G其中G'的最小顶点覆盖由A; letA(G*)表示这个顶点覆盖的大小。针对矛盾，我们假设

A(G*) >= tau(G*) + k

持有。这意味着

A(G') >= (k + 1) A(G*)
      >= (k + 1) (tau(G*) + k)
       = (k + 1) (tau(G) + k)
       = (k + 1) tau(G) + k + k^2
       > (k + 1) tau(G) + k

持有，因为k > 0持有。这与 的近似质量相矛盾A。这意味着

A(G*) < tau(G*) + k

持有。保持不变tau(G*) = tau(G)，这意味着我们已经A生成了一个G基数严格小于的顶点覆盖

tau(G) + k

这是一个矛盾，因为k被最小化地选择并且所有构造步骤都可以在多项式有界的运行时间内执行，从而导致运行时边界也是多项式有界的。

于 2017-04-07T07:58:25.200 回答