顶点覆盖的近似算法

Question

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

Answer 1

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

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

成立，其中A(G)是由A生成的G的顶点覆盖的基数，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*为G'中G的同构副本，具有A生成的最小顶点覆盖；让 A(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 被选择得最少，并且所有构造步骤都可以在多项式有界的运行时间内执行，从而导致运行时限制也有多项式限制。

Approximation Algorithm for Vertex Cover