第三十五章

34.5.2 节定义了顶点覆盖问题并且证明了它是 NP 完全的。无向图的顶点覆盖是一个子集，使得若两个顶点间存在边，则该子集至少包含这两个顶点中的一个。顶点覆盖问题是在给定的无向图中找出一个具有最小规模的顶点覆盖。我们称这样的顶点覆盖为最优顶点覆盖。顶点覆盖问题是一个 NP 完全判定问题的最优化形式。

尽管没有确切的方法在多项式时间内找到图G中的最优顶点覆盖，但有一种有效的算法可以找到接近最优的顶点覆盖。近似算法 APPROX-VERTEX-COVER 将无向图 G 作为输入，并返回一个规模一定不超过最优顶点覆盖规模的两倍的顶点覆盖。

过程 APPROX-VERTEX-COVER 的伪代码如下：初始化一个空集 C 作为顶点覆盖，初始化 E 为边集 E 的副本。然后，使用 while 循环从 E 中选择一条边，并将其两个端点加入 C，同时删除 E 中所有与其端点关联的边。最终返回顶点覆盖 C。若使用邻接表来表示图，APPROX-VERTEX-COVER 的运行时间为多项式时间。

定理 35.1 表明 APPROX-VERTEX-COVER 是一个多项式时间的 2 近似算法。证明指出，APPROX-VERTEX-COVER 的运行时间是多项式的，而返回的顶点覆盖 C 覆盖了 G 中的每条边。由此，C 是一个顶点覆盖。进一步地，证明说明了对于任意顶点覆盖 C*，APPROX-VERTEX-COVER 返回的顶点覆盖 C 的规模至多是 C* 的两倍。这表明，最优顶点覆盖的规模下界为 |A|，其中 A 是第 4 行中选取的边集。另一方面，C 的规模上界为 |A| * 2，因此，返回的顶点覆盖规模是 C* 的两倍。

回顾证明过程，我们无需确切知道最优顶点覆盖的确切规模来证明 APPROX-VERTEX-COVER 返回的顶点覆盖规模至多是最优顶点覆盖规模的两倍。只需找到最优顶点覆盖规模的下界，这通过极大匹配实现，极大匹配是指在该匹配中添加任意一条边都不能形成新的匹配的匹配。APPROX-VERTEX-COVER 算法返回的顶点覆盖规模至多为极大匹配 A 的规模的两倍。

练习题35.1-1要求给出一个使得 APPROX-VERTEX-COVER 总是产生次优解的图的例子。解答指出，构造一个二分图，左边顶点集合中的点的度数相同，右边顶点集合中的点的度数不相同。在这种情况下，APPROX-VERTEX-COVER 返回的顶点覆盖的规模恰为最优覆盖的两倍。

练习题35.1-2要求证明 APPROX-VEREX-COVER 的第 4 行中选取的边集是图 G 中的一个极大匹配。解答明确指出，第 4 行中选取的边形成了匹配，因为从 E 中选取边意味着它们与 C 中已经存在的任意一个顶点不共享端点。同时，这种匹配是最大的，因为如果将任意一条被删除的边添加到当前已选取的边的集合形成的匹配中，该匹配将不再是匹配。

练习题35.1-3探讨了一种启发式算法，重复选择度数最高的顶点，然后删除其所有关联边。解答构造了一个二分图，通过示例说明了该启发式算法的近似比不为 2。

练习题35.1-4要求给出一种有效的贪心算法，该算法能在线性时间内找到一棵树中的一个最优顶点覆盖。解答提供了两种基于后序遍历和层序遍历的贪心算法。这两种算法在处理树结构时均能返回最优顶点覆盖。

练习题35.1-5探讨了顶点覆盖问题与最大团问题的互补关系。解答指出，一个最优顶点覆盖可以是补图中最大规模团的补，但这一关系并未直接证明存在具有常数近似比的多项式时间近似算法。目前，这仍是一个未解决的问题。