algorithm - 最小顶点覆盖

Question

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

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

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

Answer 1

Here's an idea, but I have no idea if it is an improvement in practice:

From 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." Furthermore, you can compute such a decomposition in linear time.

I suggest that when you marry and remove two vertices you do this only for two vertices within the same biconnected component. When you have run out of vertices to merge you will have a set of trees not connected with each other. The vertex cover problem on trees is tractable via dynamic programming: for each node compute the cost of the best answer if that node is added to the cover and if that node is not added to the cover. You can compute the answers for a node given the best answers for its children.

Another way - for all I know better - would be to compute the minimum spanning tree of the graph and to use dynamic programming to compute the best vertex cover for that tree, neglecting the links outside the tree, remove the covered links from the graph, and then continue by marrying vertices as before.

I think I prefer the minimum spanning tree one. In producing the minimum spanning tree you are deleting a small number of links. A tree with N nodes had N-1 links, so even if you don't get back the original tree you get back one with as many links as it. A vertex cover for the complete graph is also a vertex cover for the minimum spanning tree so if the correct answer for the full graph has V vertices there is an answer for the minimum spanning tree with at most V vertices. If there were k random edges added to the tree there are k edges (not necessarily the same) that need to be added to turn the minimum spanning tree into the full graph. You can certainly make sure these new edges are covered with at most k vertices. So if the optimum answer has V vertices you will obtain an answer with at most V+k vertices.

Answer 2

这是一个精确答案的尝试，当只添加少量链接时，或者当它们不会改变节点间距离时，它是易于处理的。

找到最小生成树，并将边分为“树边”和“添加边”，其中树边形成最小生成树，添加边不为此选择。它们可能不是在构造过程中实际添加的边缘，但这并不重要。N 个节点上的所有树都有 N-1 条边，因此我们添加的边数与创建期间使用的边数相同，即使不是相同的边。

现在假装你可以偷看书后的答案，足以看到，对于每个添加的边的一个顶点，该顶点是否是最佳顶点封面的一部分。如果是，您可以从问题中删除该顶点及其链接。如果不是，则必须是另一个顶点，以便您可以从问题中删除它及其链接。

您现在必须为一棵树或许多断开连接的树找到一个最小顶点覆盖，我们知道如何做到这一点 - 请参阅我的其他答案以获得更多手波。

如果您无法从书后偷看答案，并且有 k 个附加边，请尝试书后可能出现的所有 2^k 个可能的答案并找到最佳答案。如果幸运，那么添加的链接 A 与添加的链接 B 位于不同的子树中。在这种情况下，您可以将添加链接 A（或 B）的两种可能性所需的两个计算限制为相关子树的动态规划计算，因此你只是把工作翻了一番，而不是翻了两番。一般来说，如果你添加的 k 个边在 k 个不相互干扰的不同子树中，则成本乘以 2 而不是 2^k。

Answer 3

最小顶点覆盖是一个 NP 完全算法，这意味着即使是 100 个顶点（更不用说 50k），您也无法在合理的时间内解决它。

对于一棵树，有一个基于 DFS 的多项式时间贪心算法，但是您“添加了随机边”这一事实将一切搞砸了，使该算法毫无用处。

维基百科有一篇关于近似算法的文章，声称它达到了因子 2，并声称没有更好的算法是已知的，这使得你不太可能找到一个。