顶点覆盖的近似算法

Question

如果P不等于NP可以证明没有近似算法进入最佳顶点覆盖的k，其中k是一个固定的常数？

Answer 1

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

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

成立，其中A(G)是由A和tau(G)产生的G顶点覆盖的基数表示最小顶点覆盖的基数。假设k相对于所述算法的存在被选择为最小。特别是，我们有k => 1，否则顶点覆盖问题可以在多项式时间内解决，除非P=NP成立，否则这是不可能的。

让G是一个仲裁图;通过采取k+1G的同构副本创建图表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最低限度地选择和所有施工步骤可以在一个进行多项式有界的运行时间，从而产生多项式有界的运行时间界限。