algorithm - 最小顶点覆盖

Question

我正在尝试为具有 50,000 个顶点的“几乎”树获取顶点覆盖。该图生成为一棵树，添加了随机边使其“几乎”成为一棵树。

我使用了近似方法，将两个顶点结合起来，将它们添加到封面并从图形中删除它们，然后移动到另一组顶点。之后，我尝试通过删除所有邻居都在顶点覆盖范围内的顶点来减少顶点的数量。

我的问题是如何使顶点覆盖更小？我正在尝试尽可能低。

Answer 1

这是一个想法，但我不知道它是否是实践中的改进:

来自 https://en.wikipedia.org/wiki/Biconnected_component “任何连接的图都会分解成双连接组件的树，称为图的 block 切割树。”此外，您可以在线性时间内计算此类分解。

我建议当您结合和删除两个顶点时，您只对同一双连通组件中的两个顶点执行此操作。当您用完所有要合并的顶点时，您将拥有一组彼此不连接的树。树上的顶点覆盖问题可以通过动态规划处理:对于每个节点，计算最佳答案的成本，如果该节点被添加到覆盖中，如果该节点没有被添加到覆盖中。您可以计算给定子节点最佳答案的节点的答案。

另一种方法 - 据我所知 - 是计算图的最小生成树并使用动态规划计算该树的最佳顶点覆盖，忽略树外部的链接，从中删除覆盖的链接图形，然后像以前一样继续合并顶点。

我想我更喜欢最小生成树。在生成最小生成树时，您正在删除少量链接。一棵有 N 个节点的树有 N-1 个链接，所以即使你没有取回原始树，你也会取回一个链接与它一样多的树。完整图的顶点覆盖也是最小生成树的顶点覆盖，因此如果完整图的正确答案有 V 个顶点，则最小生成树的答案最多有 V 个顶点。如果有 k 个随机边添加到树中，则需要添加 k 个边(不一定相同)以将最小生成树变成完整图。您当然可以确保这些新边最多被 k 个顶点覆盖。因此，如果最佳答案有 V 个顶点，您将获得最多有 V+k 个顶点的答案。