顶点覆盖问题的 NP 完全证明和顶点覆盖优化问题的近似算法
顶点覆盖（VERTEX COVER）
给定一个无向图
),( EVG �
和一个正整数
k
，若存在
VV �'
，
kV �'
，使得对
任意的
Evu �),(
，都有
'Vu �
或
'Vv �
，则称
'V
为图
G
的一个大小为
k
的顶点覆
盖。
顶点覆盖问题的描述
判定问题：VERTEX COVER
输 入：无向图
),( EVG �
，正整数
k
问 题：
G
中是否存在一个大小为
k
的顶点覆盖，这是一个 NP 完全问题
顶点覆盖的 NP 完全性证明
NP 性的证明：
对给定的无向图
),( EVG �
，若顶点
VV �'
是图
G
的一个大小为
k
顶点的覆
盖，则可以构造一个确定性的算法，以多项式的时间验证
kV �'
，及对所有的
Evu �),(
，是否有
'Vu �
或
'Vv �
。因此顶点覆盖问题是一个 NP 问题。
完全性的证明：
我们已知团集（CLIQUE）问题是一个 NP 完全问题，若团集问题归约于顶点
覆盖问题，即
VERTEXCLIQUE
poly
�
COVER
，则顶点覆盖问题就是一个 NP 完全
问题。
我们可以利用无向图的补图来说明这个问题。若向图
),( EVG �
，则
G
的补
图
��
� ),( EVG
，其中
}),(|),{( EvuvuE ��
�
。例如，图 1(b)是图 1(a)的补图。在图
1(a)中有一个大小为 3 的团集
},,{ yvu
，在图 1(b)中，则有一个大小为 2 的顶点
覆盖
},{ wv
。显然可以在多项式时间里构造图
G
的补图
�
G
。因此，只要证明图
),( EVG �
有一个大小为
kV �||
的团集，当且仅当它的补图
�
G
有一个大小为
k
的
顶点覆盖。
u v
w
yx
u v
w
yx
(a) (b)
图 1 无向图及补图
必要性：如果
G
中有一个大小为
kV �||
的团集，则它具有一个大小为
kV �||
个顶点的完全子图，令这
kV �||
个顶点集合为
'V
。令
),( vu
是
�
E
中的任意一条边，
则
Evu �),(
。所以
),( vu
中必有一个顶点不属于
'V
，即
),( vu
中必有一个顶点属于
'VV �
，也就是边
),( vu
被
'VV �
覆盖。因为
),( vu
是
�
E
中的任意一条边，因此，
�
E
