独立集与顶点覆盖之间的归约
【独立集问题(Independent set)】
一个独立集(也称为稳定集)是一个图中一些两两不相邻的顶点所形成的集合。即顶点集合的任意两个点之间没有边。如图1,红色的点集合都是独立集,任意两个红色的顶点没有边。
在这里插入图片描述
图1 独立集(红色)
【顶点覆盖问题】
图的顶点覆盖也是一个点的集合。图中每一条边都至少有一个顶点在点集合中。如图2,黑色的点集合都是顶点覆盖集合,图的每一条边都至少有一个顶点在点集合中。
在这里插入图片描述
图2 顶点覆盖集(黑色)
【独立集与顶点覆盖之间的归约】
独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗?
顶点覆盖问题:给定图G和数k,G是否包含大小为k的顶点覆盖?
证明两个问题的难度是等价的。
定理3:设G=(V,E)是一个图,S\subseteq V,则S是一个独立集当且仅当它的补图V-S是一个顶点覆盖。
证明:
设S是一个独立集,考虑任意的一条边,因为S是独立集,则u和v不可能都在S中,因此u和v必有一个在V-S中。则每一条至少有一个端点在V-S中,即V-S是一个点覆盖集合。
反过来,假设V-S是一个顶点覆盖。考虑S中的任意两个顶点u和v,如果它们之间有一条边e,则e的两个端点都不在V-S中,则与假设V-S是一个顶点覆盖矛盾。因此,S中的任何两个顶点之间都没有边,则S是一个独立集。
【独立集\leq_p顶点覆盖问题】
证明如果有一个解顶点覆盖的黑盒子,则通过问黑盒子G是否有大小至多为n-k的顶点覆盖,可以确定G是否有大小至少为k的独立集。
【顶点覆盖\leq_p独立集问题】
证明如果有一个解独立集的黑盒子,则通过问黑盒子G是否有大小至多为n-k的独立集,就能够确定G是否有大小至少为k的独立集。

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。