顶点覆盖

1. Introduction

一个顶点覆盖(Vertex Cover, VC)是一个连通的无向加权/无向无权图G顶点子集V,使得G中的每一条边至少有一个端点在V中。图G最小顶点覆盖(Minimum Vertex Cover, MVC)(对于加权变体,是最小权重顶点覆盖(Minimum Weight Vertex Cover, MWVC))是所有可能的VC中,具有最小基数(如果是无权的)或总权重(如果是加权的)的VC。一个图可以有多个VC,但其MVC/MWVC的基数/总权重是唯一的。


还有另一个问题叫做最大独立集(Maximum Independent Set, MIS),它试图找到一个加权/无权图G中没有任何相邻顶点的最大顶点子集。有趣的是,一个图的MVC的补集就是一个MIS


在每次可视化结束时,当一个算法突出显示当前显示的图的MVC解决方案时,它会以橙色高亮显示。对于非近似解,可视化还将突出显示MIS解(即V \\ MVC),并以浅蓝色高亮显示。


MVC,MWVC,MIS,(和MWIS)都是NP-hard组合优化问题。

1-1. 两种模式

有两种可用的模式:无权重(默认)和有权重。您可以通过点击相应的标签来在两种模式之间切换。


有些算法在两种模式下都能工作,也有些算法只能在某一种模式下工作。

2. 可视化

在这里查看所选MVC算法的可视化。


最初,输入图中的所有顶点和边都用标准黑色轮廓着色。随着可视化的进行,浅蓝色将被用来表示已覆盖的边,而边上的橙色将被用来显示已遍历的边。


在所选MVC算法结束时,如果它找到一个最小 VC,它将用橙色高亮显示MVC顶点,用浅蓝色高亮显示非MVC顶点(也称为MIS顶点)。否则,如果找到的顶点覆盖未被证明为最小的(例如,使用的算法是近似算法),它将用橙色高亮显示属于找到的顶点覆盖的顶点,而不高亮显示MIS顶点。

3. 输入

有两种不同的方式来指定输入图:

  1. 编辑图:您可以将当前显示的无向图(对于MWVC模式为加权)编辑为任何其他无向图(对于MWVC模式为加权)。
  2. 示例图:您可以从示例无向图(对于MWVC模式为加权)的列表中选择,以便开始。

4. 暴力法

暴力法:它尝试所有可能的 2^V 顶点子集。在每次迭代中,它检查当前选定的顶点子集是否是一个有效的顶点覆盖,通过遍历所有 E 边并在 O(E) 中检查所有边是否被当前选定的子集中的顶点覆盖。这种暴力算法保持有效顶点覆盖的最小大小作为答案。


这种暴力算法在加权和未加权版本中都可用。


它的时间复杂度是 O(2^V × E),即,极其慢。我们正在改进可视化,以便剪掉"无聊"的非改进部分,只突出显示重要的"候选 VC"子集。


讨论:但是,如果我们被告知 k '不是那么大',那么有一个替代的 O(2^k × E) 参数化解决方案。

4-1. 参数化解决方案

遗憾的是,这部分还没有被数字化/可视化,正在进行中。


请参阅 CS4234 的讲义以获取详细信息。

5. 树上的DP

树上的DP:如果图是一棵,那么MVC问题可以被构造为一个动态规划问题,其中的状态是(位置,取当前顶点)。


然后,可以看出:
DP(u, take) = cost[u] + sum(min(DP(v, take), DP(v, not_take))) ∀child v of u, 和
DP(u, not take) = sum(DP(v, take)) ∀child v of u


这个DP算法在加权和未加权版本中都可用。


它的时间复杂度是O(V),即非常快,但前提是输入图是一棵树。

6. 树上贪婪 MVC

树上的贪心 MVC:再次强调,如果图是一个无权重,我们可以通过观察到,如果有任何 MVC 解决方案包含一个叶子顶点,我们可以通过取代该叶子顶点的父顶点来得到一个“不差”的解决方案。在移除所有被覆盖的顶点后,我们可以应用同样的观察并重复它,直到每个顶点都被覆盖。


这种贪心 MVC 算法只在无权重模式下可用。


它的时间复杂度是 O(V),即非常快,但前提是输入图是一个无权重的树。

7. Kőnig定理

柯尼希定理:根据柯尼希定理,无权二分图中的最小顶点覆盖(MVC)的大小等于二分图的最大匹配的基数。在加权二分图的情况下,我们可以看到这个定理也同样成立,只是我们构建图的方式有所改变。在这个可视化中,我们使用减少到最大流问题来获取MVC的值。


这个算法在加权和无权版本中都可用。


它的时间复杂度是 O(V × E)(对于无权版本;预处理后可能会更小)或 O(E^2 × V)/O(V^2 × E)(对于加权版本,取决于使用的最大流算法)。

8. 近似算法

我们有几种已知的 MVC 近似算法:

  1. 对于无权版本,我们有确定性的2倍近似或概率性的2倍近似(期望值),
  2. 对于加权版本,我们有 Bar-Yehuda 和 Even 的2倍近似算法。

请注意,这些算法只能得到一个"近似"的 MVC,意味着它们并不是真正的最小顶点覆盖,但足够好。

8-1. 近似比证明

遗憾的是,这部分还没有数字化,正在进行中。


请查看 CS4234 的讲义以获取详细信息。