最小顶点覆盖
Minimum vertex cover
我正在尝试为具有 50,000 个顶点的 "almost" 树获取顶点覆盖。该图生成为一棵树，并添加了随机边使其 "almost" 成为一棵树。
我使用了近似方法，将两个顶点结合起来，将它们添加到封面并将它们从图中移除，然后移动到另一组顶点。之后，我尝试通过删除所有邻居都在顶点覆盖范围内的顶点来减少顶点的数量。
我的问题是如何使顶点覆盖更小？我正在尝试尽可能低。
这是一个想法，但我不知道它是否是实践中的改进：
来自https://en.wikipedia.org/wiki/Biconnected_component "Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph." 此外，您可以在线性时间内计算这种分解。
我建议当你结合和删除两个顶点时，你只对同一个双连通组件中的两个顶点执行此操作。当您有 运行 个要合并的顶点时，您将拥有一组彼此不连接的树。树上的顶点覆盖问题可以通过动态规划处理：对于每个节点，计算最佳答案的成本，如果该节点被添加到覆盖中，如果该节点没有被添加到覆盖中。您可以计算给定子节点最佳答案的节点的答案。
另一种方法 - 据我所知 - 是计算图形的最小生成树并使用动态编程计算该树的最佳顶点覆盖，忽略树外部的链接，删除覆盖从图中链接，然后像以前一样继续合并顶点。
我想我更喜欢最小生成树。在生成最小生成树时，您正在删除少量链接。一棵有 N 个节点的树有 N-1 个链接，所以即使你没有取回原始树，你也会取回一个链接与它一样多的树。完整图的顶点覆盖也是最小生成树的顶点覆盖，因此如果完整图的正确答案有 V 个顶点，则最小生成树的答案最多有 V 个顶点。如果有 k 个随机边添加到树中，则需要添加 k 个边（不一定相同）以将最小生成树变成完整图。您当然可以确保这些新边最多被 k 个顶点覆盖。因此，如果最佳答案有 V 个顶点，您将获得最多 V+k 个顶点的答案。
最小顶点覆盖是一个NP完全算法，这意味着即使是100个顶点（更不用说50k），你也无法在合理的时间内解决它。
对于一棵树，有一个基于 DFS 的多项式时间贪婪算法，但事实上你有 "random edges added" 搞砸了一切，使这个算法无用。
Wikipedia has an article about approximation algorithm，声称它达到了因子 2 并声称没有更好的算法，这使得你不太可能找到一个。
这是一个精确答案的尝试，当只添加少量 link 时，或者当它们不会改变节点间距离时，它是易于处理的。
求一棵最小生成树，将边分为"tree edges"和"added edges"，其中树边组成最小生成树，为此不选择添加的边。它们可能不是在构造过程中实际添加的边缘，但这并不重要。 N 个节点上的所有树都有 N-1 条边，因此我们添加的边数与创建期间使用的边数相同，即使边数不同。
现在假设您可以偷看书后的答案，对于每条添加的边的一个顶点，该顶点是否是最佳顶点覆盖的一部分。如果是，您可以从问题中删除该顶点及其 links。如果不是，另一个顶点必须是这样你可以从问题中删除它和它的 links。
你现在必须找到一棵树或许多不相连的树的最小顶点覆盖，我们知道如何做到这一点 - 请参阅我的其他答案以获得更多帮助。
如果你不能从书的后面偷看答案，并且有 k 个附加边，请尝试所有 2^k 个可能已经在书的后面的答案，并找到最好的答案。如果幸运的话，添加 link A 与添加 link B 在不同的子树中。在这种情况下，您可以限制添加 link A 的两种可能性所需的两种计算（或B) 相关子树的动态规划计算，因此您只将工作加倍而不是四倍。一般来说，如果你添加的 k 条边在 k 个互不干扰的不同子树中，则成本乘以 2 而不是 2^k。
我正在尝试为具有 50,000 个顶点的 "almost" 树获取顶点覆盖。该图生成为一棵树，并添加了随机边使其 "almost" 成为一棵树。
我使用了近似方法，将两个顶点结合起来，将它们添加到封面并将它们从图中移除，然后移动到另一组顶点。之后，我尝试通过删除所有邻居都在顶点覆盖范围内的顶点来减少顶点的数量。
我的问题是如何使顶点覆盖更小？我正在尝试尽可能低。
这是一个想法，但我不知道它是否是实践中的改进：
来自https://en.wikipedia.org/wiki/Biconnected_component "Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph." 此外，您可以在线性时间内计算这种分解。
我建议当你结合和删除两个顶点时，你只对同一个双连通组件中的两个顶点执行此操作。当您有 运行 个要合并的顶点时，您将拥有一组彼此不连接的树。树上的顶点覆盖问题可以通过动态规划处理：对于每个节点，计算最佳答案的成本，如果该节点被添加到覆盖中，如果该节点没有被添加到覆盖中。您可以计算给定子节点最佳答案的节点的答案。
另一种方法 - 据我所知 - 是计算图形的最小生成树并使用动态编程计算该树的最佳顶点覆盖，忽略树外部的链接，删除覆盖从图中链接，然后像以前一样继续合并顶点。
我想我更喜欢最小生成树。在生成最小生成树时，您正在删除少量链接。一棵有 N 个节点的树有 N-1 个链接，所以即使你没有取回原始树，你也会取回一个链接与它一样多的树。完整图的顶点覆盖也是最小生成树的顶点覆盖，因此如果完整图的正确答案有 V 个顶点，则最小生成树的答案最多有 V 个顶点。如果有 k 个随机边添加到树中，则需要添加 k 个边（不一定相同）以将最小生成树变成完整图。您当然可以确保这些新边最多被 k 个顶点覆盖。因此，如果最佳答案有 V 个顶点，您将获得最多 V+k 个顶点的答案。
最小顶点覆盖是一个NP完全算法，这意味着即使是100个顶点（更不用说50k），你也无法在合理的时间内解决它。
对于一棵树，有一个基于 DFS 的多项式时间贪婪算法，但事实上你有 "random edges added" 搞砸了一切，使这个算法无用。
Wikipedia has an article about approximation algorithm，声称它达到了因子 2 并声称没有更好的算法，这使得你不太可能找到一个。
这是一个精确答案的尝试，当只添加少量 link 时，或者当它们不会改变节点间距离时，它是易于处理的。
求一棵最小生成树，将边分为"tree edges"和"added edges"，其中树边组成最小生成树，为此不选择添加的边。它们可能不是在构造过程中实际添加的边缘，但这并不重要。 N 个节点上的所有树都有 N-1 条边，因此我们添加的边数与创建期间使用的边数相同，即使边数不同。
现在假设您可以偷看书后的答案，对于每条添加的边的一个顶点，该顶点是否是最佳顶点覆盖的一部分。如果是，您可以从问题中删除该顶点及其 links。如果不是，另一个顶点必须是这样你可以从问题中删除它和它的 links。
你现在必须找到一棵树或许多不相连的树的最小顶点覆盖，我们知道如何做到这一点 - 请参阅我的其他答案以获得更多帮助。
如果你不能从书的后面偷看答案，并且有 k 个附加边，请尝试所有 2^k 个可能已经在书的后面的答案，并找到最好的答案。如果幸运的话，添加 link A 与添加 link B 在不同的子树中。在这种情况下，您可以限制添加 link A 的两种可能性所需的两种计算（或B) 相关子树的动态规划计算，因此您只将工作加倍而不是四倍。一般来说，如果你添加的 k 条边在 k 个互不干扰的不同子树中，则成本乘以 2 而不是 2^k。