顶点覆盖

在图论中，顶点覆盖（或节点覆盖）是指图中包含每条边的至少一个端点的顶点集合。

寻找最小顶点覆盖是计算机科学中的一个经典优化问题。如果 P ≠ N.P.，那么它是 NP 难的，不能通过多项式时间方法解决。此外，如果唯一博弈假设成立，那么它很难近似——只能近似到两倍。然而，它包含一些简单的 2-因子近似。它是 NP 难近似方法优化问题的经典示例。它的决策变体，即顶点覆盖问题，是计算复杂性理论中的一个著名 NP 完全问题，因为它曾是 Karp 的 21 个 NP 完全问题之一。顶点覆盖问题也是参数化复杂性理论中的一个关键问题，并且是固定参数可解的。

最大匹配问题是半整数线性规划的对偶线性规划，可用于表示最小顶点覆盖问题。

超图也存在顶点覆盖问题；更多信息请参阅超图中的顶点覆盖。

示例

• 所有顶点的集合是一个顶点覆盖。
• 任何最大匹配的端点都形成一个顶点覆盖。
• 完整二分图的顶点覆盖至少是。

性质

对于一个顶点集合来说，要成为一个顶点覆盖，它的对应集合也必须是一个独立集。因此，最大独立集的大小加上最小顶点覆盖数等于图中顶点的数量（Gallai 1959）。

计算问题

在给定图中寻找最短顶点覆盖的优化挑战是最小顶点覆盖问题。

实例： 输出具有特定大小顶点覆盖的最小整数图。

如果以选择问题的形式呈现，该问题被称为顶点覆盖问题

示例： 带有正整数的图。

它是否有一个最多达到特定大小的顶点覆盖？

顶点覆盖问题是 Karp 的 21 个 NP 完全问题之一，是一个 NP 完全问题。它在计算机复杂性理论中经常用作 NP 难性论证的基础。

ILP 开发

假设每个顶点都有一个相应的成本。以下整数线性规划 (ILP) 可以表示（加权）最小顶点覆盖问题。

这个 ILP 属于解决更广泛问题的 ILP 类别。放宽此 ILP（允许每个变量在 0 到 1 的范围内，而不仅仅是要求变量为 0 或 1）会为最小顶点覆盖问题提供一个因子近似解，因为此 ILP 的整数间隙是。对于每个输入，存在一个理想的解，其值要么是 0、1/2 或 1，并且该 ILP 的线性规划松弛是半整数的。可以通过选择变量为非零的顶点子集，从这个分数解构造一个 2-近似顶点覆盖。

精确评估

由于基于决策的顶点覆盖问题是 NP 完全的，因此不太可能存在一种有效的方法来精确解决不同图的问题。可以通过从 3-可满足性进行归约，或者如 Karp 所证明的，从团问题进行归约来证明 NP 完全性。即使在三次图[2]中，甚至在最大度为三的平面图中，顶点覆盖仍然是 NP 完全的。

由于 König 定理概述的顶点覆盖和最大匹配之间的等价性，二分图的二分顶点覆盖问题可以在多项式时间内解决。

为了找到树图的最小顶点覆盖，一种算法会找到树中的第一个叶子，将其添加到最小顶点覆盖中，然后删除该叶子、其父节点以及相关的边。这个过程会一直持续到树中没有边为止。

固定参数可追踪性

使用穷举搜索技术，该问题可以在时间 2^kn^O(1) 内解决，其中 k 是顶点覆盖的大小。因此，如果只对小的 k 感兴趣，则顶点覆盖是固定参数可追踪的，并且我们可以在多项式时间内解决该问题。在这种情况下，一种有效的算法方法是受约束搜索树方法，其思想是定期选择一个顶点并递归分支，每个步骤有两种情况：将当前顶点或其所有邻居插入到顶点覆盖中。实现最佳渐近参数依赖的顶点覆盖技术在时间复杂度范围内运行。

对于这个时间限制，可以在可接受的时间长度内解决的最大参数值，即声明值，是 190。换句话说，除非有进一步的算法改进，否则这种方法仅适用于顶点覆盖数小于或等于 190 的情况。指数时间假设是一个可行的复杂性理论假设，它阻止了运行时间增加到 2^o(k)，即使它也是如此。

对于平面图，更广泛地来说，对于不包含某个固定图作为子式的图，可以在时间内找到大小为 k 的顶点覆盖，这表明该问题是亚指数固定参数可解的。由于在指数时间假设下，没有算法可以在时间内解决平面图上的顶点覆盖问题，因此这种技术再次是最优的。

粗略评估

通过重复将一条边的两端插入顶点覆盖并从图中删除它们，可以获得一个 2 因子近似。换句话说，使用贪婪方法，我们确定一个最大匹配 M，并创建一个由 M 中每个边的端点组成的顶点覆盖 C。在附图中，最大匹配 M 和顶点覆盖 C 用红色和蓝色突出显示。

这会为集合 C 创建一个顶点覆盖：考虑一条边 e 未被 C 覆盖的情况。在这种情况下，M ∪ {e} 是一个匹配，并且 e ∉ M，这与 M 是最大匹配的概念不一致。此外，每个顶点覆盖，即使是理想的顶点覆盖，也必须包含 u 或 v（或两者），否则如果 e = {u, v} ∉ M，则边 e 未被覆盖。因此，理想覆盖在 M 中每条边至少有一个端点，并且集合 C 的总大小不超过最优顶点覆盖的两倍。

Fanica Gavril 和 Mihalis Yannakakis 分别提出了这个简单的方法。

更复杂的算法表明存在具有更优近似因子的近似方法。例如，已知的一种近似算法的近似因子是。密集图可以用作近似因子来近似该问题。

不可近似性

上述方法是目前最好的常数因子近似方法。最小顶点覆盖问题是 APX 完全的，这意味着除非 P = N.P.，否则它不能被任意近似。Dinur 和 Safra 在 2005 年证明，使用 PCP 定理的方法，除非 P = N.P.，否则对于任何足够大的顶点度数，最小顶点覆盖不能在 1.3606 的因子内计算。后来，该因子被修改为适用于所有人。此外，根据唯一博弈猜想，最小顶点覆盖不能在任何优于 2 的常数因子内进行估计。

尽管如前所述，寻找最大独立集等同于寻找最小顶点覆盖，但这两个问题在保持近似值的方式上并不具有可比性：除非 P = N.P.，否则独立集问题没有常数因子近似。

伪代码

应用

许多理论和实际问题都可以使用顶点覆盖优化技术进行建模。例如，一个商业机构可以将目标表示为顶点覆盖归约问题，以确定应该安装多少闭路摄像机来覆盖连接一个楼层所有房间（节点）的所有走廊（边）。该问题还被用作合成生物学和代谢工程应用中去除重复 DNA 序列的模型。

树的最小顶点覆盖

根据 Miguel. Martin，对 的引用存在算法错误。我创建了另一种方法来实现这一点，但找不到任何参考资料；我在以色列开放大学一门课程的测试解决方案中发现了这个算法。——37.46.41.87（讨论）于 2016 年 6 月 4 日 11:42（UTC）添加了上述未签名评论。

将集合合并到集合覆盖中何时进行撞击？

顶点覆盖#超图中的顶点覆盖（和 k-击集问题 的 k-近似）信息是否应该与集合覆盖问题合并？许多出版物目前正在探讨集合覆盖问题近似性的方式很奇特。2009 年 11 月 9 日 22:41 (UTC) - Miym

集合覆盖和击集问题是同一问题的两种不同视角。与集合覆盖的有界频率视角相比，击集的有界边大小视角更合乎逻辑。为了改善集合覆盖问题的情况，我建议将 k-击集的 k-近似合并到 Vertex cover#hypergraphs 中的 Vertex cover。同意吗？2009 年 11 月 11 日 14:18 (UTC) - ylloh