问题标签 [vertex-cover]

我正在尝试编写一个 DP 算法来计算我们需要选择的最小顶点数，以便覆盖图上的 k 个边。

到目前为止我写的代码是：

由于某种原因，此代码产生了错误的输出。但是，如果它是正确的，我怀疑它不会很快（指数复杂度）。你能推荐一个算法吗？

示例：对于输入：9 6 1 2 1 3 1 4 2 5 2 6 3 7 4 8 4 9

预期输出为 2

我的程序输出 0。

在看到下面的答案后，我想出了以下代码：

我需要找到下一个问题的减少：

顶点覆盖 - 给定 (G=(V, E), k)-> G 是无向图，我们需要大小为 k 的 S（V 的子组）覆盖 E 中的所有边。

Hal Vertex Cover- Given (G=(V', E'), k')-> G 是无向图。并且我们需要大小为 k' 的 S'（V' 的子群）恰好覆盖 E' 中一半的边。

如果您能告诉我如何做到这一点以及为什么 Karp-Reduction 将是正确的（证明的两个方向），我会很高兴。

谢谢你。

以下属性来自 wiki 顶点覆盖：当且仅当其补集是独立集时，一组顶点才是顶点覆盖。

我想知道我们如何证明这是真的？如果它可以通过矛盾来证明，那就太好了，但所有其他证明方式也受到赞赏。

谢谢你！

我有以下问题，似乎与顶点覆盖问题有一些相似之处。

我们有一个有向图 G=(V,E) 和 |V| 顶点和 |E| 边缘。让我们假设一个顶点代表一个人，而从顶点 A 到顶点 B 的一条边代表从 B 到 A 的信息路径，即如果给 B 一条信息，那么 A 也有它。但是，如果另一条边从顶点 C 到顶点 A，则信息将不会到达 C，除非存在从 C 到 B 的边，或者如果信息也直接提供给 A。

现在的问题是，通过向（最多）k 个顶点/人提供信息，我们可以达到的最大顶点/人数是多少。我认为这与顶点问题密切相关，但我们只需要覆盖 k 个顶点而不是全部。但它似乎仍然不太适合另一个问题。

谁能说出一个具有相似结构的众所周知的问题？这将帮助我更好地接近它的近似算法。

编辑：我对这个问题的优化方面很感兴趣，但在我看来，最佳方法是选择一组尽可能大的有联系的人，然后从所有其他有联系的人集中删除选定的人人并重复这个过程。那么问题就出在 P 中，但它实际上是 NP 难的。这个我没看到。

这个问题可能和这个帖子有关。

这个问题也在这里问过，但口味不同。

考虑具有周期性边界条件的（无向）方图。然后找到一个长度等于 4 的完整循环图。现在我想从它的元素中为每个循环分配一个唯一的代表。因此，在具有 n_v 个顶点的方形图中，我会发现 n_f=n_v 4 个循环，并且 n_v 代表循环。对于方形图，一切都很简单。只需分配每个斑块的左下角（4 个循环）。

（我只显示前 4 个周期）

现在，我想将它推广到其他结构。考虑具有适当边界条件的（无向）kagome 图，

（这里我只展示了 3 个不同的周期）

在这种情况下，要将顶点分配给循环覆盖，您需要三个不同长度的循环。它以与指定顶点相似的颜色显示。但是，现在我想将其推广到其他复杂的图表。我想知道这个问题是否有名称以及它的可能性或算法。例如，我们不能在三角图中这样做：

我找到了一些算法来找到一个最小的顶点覆盖，比如使用二叉搜索树，但我读到使用三叉树更好。但我找不到任何关于它的信息或想出一个算法。

有人知道怎么做吗？

考虑到顶点集 V = {v_1, ... , v_n} 的无向图 G = (V,E)，我正在尝试为最小顶点覆盖问题提出回溯算法。给定一个 n 顶点图的邻接列表 Adj[1...n] 输出 G 的最小顶点覆盖的大小。我不想使用修剪。

我定义了参数 Adj[1..n], int i 来表示我们目前已经涵盖的 Adj 的索引，以及非负 int vertexCover 来表示顶点覆盖。我的想法是当我们覆盖 Adj[1..n] 中的所有顶点时停止，如果我们还没有完成，我想首先检查是否存在连接到 G 中所有其他顶点的顶点，因为然后这个顶点显然将是解决方案。如果不存在这样的顶点，我想将邻接列表转换为一棵树，我可以在其中递归调用我的函数来遍历树。我还在考虑创建一个 int 数组 A 来记录作为最小顶点覆盖一部分的顶点的索引。

我在下面分享我的pseducode，我目前在如何在树中进行选择时遇到问题，我相信 MinVertexCover(Adj, i + 1, vertexCover) 将遍历树（因此它将访问根的孩子），但我不确定如何决定是否包括该孩子和/或继续下一个孩子。

我有一个很难开始的家庭作业问题。我们正在研究 Karp（单次调用）减少以显示难处理性。对于这个任务，这个问题是故意模糊的。我希望这里的某个人可能知道它或者可以提供一个解决方案示例来帮助我入门。

该问题仅在他们提供的代码中进行了描述。它具有以下组件：

B = (G, T, k) 其中 B 是“Blah”问题的一个实例，G = (V,E) 是图（未加权，无向），T 是 V 中的顶点子集，k 是整数。B 的证书返回 G 的子图 S = (V', E')。还提供了 yes 实例的验证器：

一个是的例子如果

我看到这个问题与独立集或顶点覆盖问题之间有一些相似之处。我觉得这些是很好的候选者，可以减少以显示难以处理，但对问题的理解还不够好。如果在某处讨论这个问题，或者任何人都可以提供一些例子，我将不胜感激。谢谢！