问题标签 [vertex-cover]

我正在编写一个蛮力算法来解决这样的顶点覆盖：

在哪里

我在很多图上尝试这个（但它们的最大尺寸是 20 个顶点），这需要十年的时间......我可以对这个蛮力做任何优化，让它运行得更快吗？

我得到的启发式解决方案是：

• 在图上执行深度优先搜索
• 删除所有叶子
• 剩下的图形成一个顶点覆盖

我被问到这个问题：“证明这个启发式最多是顶点覆盖的最佳解决方案的两倍”。我怎样才能显示这个？

我试图找出一种算法来找到二分图的最小顶点覆盖。

我正在考虑一个解决方案，将问题减少到二分图中的最大匹配。众所周知，可以使用从 bip 创建的网络中的最大流量来找到它。图形。

最大匹配 M 应确定最小值。顶点覆盖C，但我无法应付选择顶点来设置C。让我们说bip。图有 X、Y 部分，作为最大匹配边的端点的顶点在集合 A 中，不属于 B 的那些。

我会说我应该为 M 到 C 中的一条边选择一个顶点。特别是 M 中的边 e 的端点连接到集合 B 中的顶点，否则如果它只连接到 A 中的顶点，那没关系。不幸的是，这个想法通常不起作用，因为我的算法可以找到反例，因为 A 中的顶点也可以通过 M 中包含的其他边连接。

任何帮助都将不胜感激。

我想将顶点覆盖问题简化为特定的决策问题。这个决策问题如下：

我有一个 nxn 矩阵 A、一个 R^n 中的向量 b 和一个正整数 k。R^n 中是否存在最多 k 个非零条目的向量 x，使得 A*x 大于或等于 b？

我在想 A 可以被视为一个邻接矩阵，但我不确定如何将顶点覆盖问题减少到这个问题。

谁能给我一两个关于我下一步应该做什么的提示？

编辑**我最初考虑使用支配集问题，但在考虑了更多问题之后，我认为我应该使用顶点覆盖来代替。（所以问题最初是指支配集）

我在一个简单的图表中读到，|最小顶点覆盖| <= 2*|最大匹配|。

考虑这里显示的图表：-

这里的最小顶点覆盖可以是 {B,C,D,E}，其大小为 4，最大匹配大小仅为 1。因此，4>2*1 并且该属性似乎不满足。

有人可以帮我弄这个吗？

过去通过网站上的快速搜索，已经有很多关于这个主题的帖子，其中许多都使用了这种动态编程重复：

C(x) = min(1 + sum (C(i) for i in x's children), len(x's children) + sum(C(i) for i in x's sunchildren))

假设树以节点 1 为根，我对节点链 1-2-3-4-5-6 尝试了此算法，以获得以下 C(i)：

| C(1) | C(2) | C(3) | C(4) | C(5) | C(6) |

| 3 | 2 | 2 | 1 | 1 | 1 |

但是，C(1) 的正确答案应该是 2，这是通过标记节点 2 和 5 来实现的。

我决定尝试我自己的方法，详情如下：

curr是我们所在的当前节点，height是距其上方最近的标记节点的距离。这个想法是，一旦节点的高度 = 3，就必须在该特定路径中标记它。否则，我们现在可以跳过标记它。一个例外是叶子节点，如果没有标记相邻节点，则必须标记它。

有人可以验证我的方法的有效性，并解释为什么第一个算法未能通过链测试吗？

提前致谢！

我有一个邻接A矩阵nodes = {0, 1, 2, 3, 4, 5}

我想找到这个图的最小权重顶点覆盖。我将这个邻接矩阵转换为

和下面的函数来找到vectex覆盖

但输出是

这只是所有顶点的集合。预期的输出应该是

这个过程有什么问题？

网格可以是完整 G 的示例。其中每个节点都连接到每个其他节点。因此，这种图的最小顶点覆盖大小不应该是“1”。

使用多项式时间内的最大匹配可以解决基数顶点覆盖问题吗？什么是近似系数？请帮我

问题：设 T 是一棵以某个节点 r 为根的 n 节点树。我们希望在 T 的节点上放置尽可能少的保护，以便 T 的每条边都受到保护：如果在这两个节点 v 中的至少一个上放置保护，则父节点 v 与其子节点 w 之间的边受到保护, w。给出一个 O(n) 时间算法来找到问题的最优解。

我的方法是从根进行后序遍历，并在一个节点上放置一个防护，该节点是一个无防护边的一部分，除非该节点是叶子......但是如果所有节点都排列在一个线性链，因为我的算法会在每个节点上放置保护，除了链的末端。

我在网上查看并检查了 DP 解决方案，这对我来说很有意义，但我想知道是否有一个贪心算法来找到一棵树的顶点覆盖