一个顶点覆盖（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组合优化问题。
有两种可用的模式：无权重（默认）和有权重。您可以通过点击相应的标签来在两种模式之间切换。
有些算法在两种模式下都能工作，也有些算法只能在某一种模式下工作。
在这里查看所选MVC算法的可视化。
最初，输入图中的所有顶点和边都用标准黑色轮廓着色。随着可视化的进行，浅蓝色将被用来表示已覆盖的边，而边上的橙色将被用来显示已遍历的边。
在所选MVC算法结束时，如果它找到一个最小 VC，它将用橙色高亮显示MVC顶点，用浅蓝色高亮显示非MVC顶点（也称为MIS顶点）。否则，如果找到的顶点覆盖未被证明为最小的（例如，使用的算法是近似算法），它将用橙色高亮显示属于找到的顶点覆盖的顶点，而不高亮显示MIS顶点。
有两种不同的方式来指定输入图：
暴力法：它尝试所有可能的 2^V 顶点子集。在每次迭代中，它检查当前选定的顶点子集是否是一个有效的顶点覆盖，通过遍历所有 E 边并在 O(E) 中检查所有边是否被当前选定的子集中的顶点覆盖。这种暴力算法保持有效顶点覆盖的最小大小作为答案。
这种暴力算法在加权和未加权版本中都可用。
它的时间复杂度是 O(2^V × E)，即，极其慢。我们正在改进可视化，以便剪掉"无聊"的非改进部分，只突出显示重要的"候选 VC"子集。
讨论：但是，如果我们被告知 k '不是那么大'，那么有一个替代的 O(2^k × E) 参数化解决方案。
遗憾的是，这部分还没有被数字化/可视化，正在进行中。
请参阅 CS4234 的讲义以获取详细信息。
树上的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)，即非常快，但前提是输入图是一棵树。
树上的贪心 MVC：再次强调，如果图是一个无权重的树，我们可以通过观察到，如果有任何 MVC 解决方案包含一个叶子顶点，我们可以通过取代该叶子顶点的父顶点来得到一个“不差”的解决方案。在移除所有被覆盖的顶点后，我们可以应用同样的观察并重复它，直到每个顶点都被覆盖。
这种贪心 MVC 算法只在无权重模式下可用。
它的时间复杂度是 O(V)，即非常快，但前提是输入图是一个无权重的树。
柯尼希定理：根据柯尼希定理，无权二分图中的最小顶点覆盖（MVC）的大小等于二分图的最大匹配的基数。在加权二分图的情况下，我们可以看到这个定理也同样成立，只是我们构建图的方式有所改变。在这个可视化中，我们使用减少到最大流问题来获取MVC的值。
这个算法在加权和无权版本中都可用。
它的时间复杂度是 O(V × E)（对于无权版本；预处理后可能会更小）或 O(E^2 × V)/O(V^2 × E)（对于加权版本，取决于使用的最大流算法）。
我们有几种已知的 MVC 近似算法：
请注意，这些算法只能得到一个"近似"的 MVC，意味着它们并不是真正的最小顶点覆盖，但足够好。
遗憾的是，这部分还没有数字化，正在进行中。
请查看 CS4234 的讲义以获取详细信息。