精选优质文档-倾情为你奉上顶点覆盖问题的NP完全证明和顶点覆盖优化问题的近似算法顶点覆盖（VERTEX COVER）给定一个无向图和一个正整数，若存在，使得对任意的，都有或，则称为图的一个大小为的顶点覆盖。顶点覆盖问题的描述判定问题：VERTEX COVER输 入：无向图，正整数问 题：中是否存在一个大小为的顶点覆盖，这是一个NP完全问题顶点覆盖的NP完全性证明NP性的证明：对给定的无向图，若顶点是图的一个大小为顶点的覆盖，则可以构造一个确定性的算法，以多项式的时间验证，及对所有的，是否有或。因此顶点覆盖问题是一个NP问题。完全性的证明：我们已知团集（CLIQUE）问题是一个NP完全问题，若团集问题归约于顶点覆盖问题，即，则顶点覆盖问题就是一个NP完全问题。我们可以利用无向图的补图来说明这个问题。若向图，则的补图，其中。例如，图1(b)是图1(a)的补图。在图1(a)中有一个大小为3的团集，在图1(b)中，则有一个大小为2的顶点覆盖。显然可以在多项式时间里构造图的补图。因此，只要证明图有一个大小为的团集，当且
