问题标签 [vertex-cover]

以下是Maximum Bipartite匹配问题：http ://www.spoj.com/problems/QUEST4/ 通过论坛我知道这个问题可以转换为Minimum Vertex Cover问题，然后可以通过Maximum解决双向匹配。但是，我不明白问题是如何转换为最小顶点覆盖的。请帮助我理解这一点。

在我的研究中，我遇到了以下顶点覆盖问题的变体：

给定一个图 G，一个顶点 v 和一个数 k，来决定 G 是否有一个包含 v 的大小为 k 的顶点覆盖。

我搜索了所有文献，找不到类似的问题。我对这个问题的复杂性感兴趣（我已经证明它对于 $P^NP[long]$ 是完整的）。

问题是你见过这种顶点覆盖问题的变体吗？你怎么称呼这个问题？

如何证明一个大小为 n 的团的任何最小顶点覆盖必须恰好有 n-1 个顶点？谢谢

我正在实现顶点覆盖问题的内核化算法中的优化算法：理论和实验 (PDF)。

我有点卡在第 2.3 章：Kernelization by linear programming。

这种技术的想法（在 ILP 公式中）是为输入图的X_u \in \left\{ 0,1 \right\}每个顶点u（也表示为）分配一个权重，以满足以下约束：vG=\left\( V,E \right\)

• 最小化权重总和\Sigma_uX_u
• 满足X_u + X_v \geq 1只要\left\{ u,v \right \}被图中的一条边连接。

因此，作为输出，我得到一组顶点X_v为 1，其余顶点X_v为 0。论文说，松弛是基于X_u \in \left \{ 0,1 \right \}替换X_u \geq 0。（S. Khuller (PDF)在这种情况下指出了这一点X_u \in \left \{ 0,0.5,1 \right \}）。这种放松将导致拥有 3 组权重分别为 1、0.5 和 0 的顶点。

我的问题是我不太确定如何进行重量分配。

据我所知，为了最小化权重总和，最好（对于每条边）首先关注度数最高的顶点，当它们的权重已经大于零时，将值添加到顶点分析边缘的第二端。

这使我（正确地？）进入X_v \in \left \{ 0,1 \right \}基本公式中每个顶点的实际情况。当我考虑放宽整数约束时，它只会更改为X_v \in \left \{ 0,0.5 \right \}.

我的逻辑有什么缺陷？

我需要如何进行松弛以使顶点的权重为 1 和 0 以及 0.5？

有很多算法可以找到图的顶点覆盖，但是想知道可以用作在大图上找到顶点覆盖的并行方法的最佳算法，那么哪个最好？正如我问过这个问题，因为这个问题在实际应用中的重要性更像是在恐怖主义通信 N/w、航空公司通信 N/w、无线通信等中。

树上的顶点覆盖问题如下。

输入：无环简单无向图 G
输出：一组顶点 W 使得对于每条边 uv，u ∈ W 或 v ∈ W。我们希望最小化 W 的大小。

我的贪心算法是初始化 W = ∅，然后，当 G 不为空时，重复以下步骤。令 L 为 G 的叶顶点。令 N(L) 为与 L 中某个顶点相邻的顶点集。更新 W = W ∪ N(L)。从 G 中删除顶点 L ∪ N(L) 及其入射边。

该算法适用于我迄今为止尝试过的所有情况。我该如何证明它是正确的？这是我到目前为止所拥有的。

假设有另一个集合 S 是最优解。相反，我想确定 S 没有覆盖所有边缘，或者 S 与我的贪婪算法产生的集合相同。

我正在努力解决这个问题......下面提到的是一种算法......我想出了......

输入一个图，选择一个与所有其他节点匹配度最高的顶点。移除在该节点上发生的边。将选定的顶点及其边添加到集合 X。返回 X

X 返回顶点覆盖所需的最小顶点集。这种方式是否正确......？谢谢

存在一个处理树的问题，其中顶点的权重是它的度数，但我对顶点可以具有任意权重的情况感兴趣。

这不是家庭作业，但它是我目前正在阅读的算法设计手册中的问题之一；答案集给出了解决方案

1. 执行 DFS，在每一步更新 Score[v][include]，其中 v 是一个顶点，include 是真或假；
2. 如果 v 是叶子，设置 Score[v][false] = 0, Score[v][true] = w _v，其中 w _v是顶点 v 的权重。
3. 在DFS期间，当从节点v的最后一个子节点向上移动时，更新Score[v][include]：Score[v][false] = Sum for c in children(v) of Score[c][true] and Score [v][true] = w _v + 子项中 c 的总和 (v) of min(Score[c][true]; Score[c][false])
4. 通过回溯分数提取实际覆盖。

但是，我实际上无法将其转化为有效的东西。（回应评论：到目前为止，我尝试的是绘制一些带有权重的小图并在纸上运行算法，直到第四步，其中“提取实际封面”部分不透明。）

作为回应阿里的回答：所以假设我有这个图，由A等给出的顶点和括号中的权重：

A(9)---B(3)---C(2) \ \ E(1) D(4)

正确答案是明确的{B,E}。

通过这个算法，我们会像这样设置值：

• score[D][false] = 0;score[D][true] = 4
• score[C][false] = 0;score[C][true] = 2
• score[B][false] = 6;score[B][true] = 3
• score[E][false] = 0;score[E][true] = 1
• score[A][false] = 4;score[A][true] = 12

好的，所以，我的问题基本上是，现在呢？做简单的事情并遍历score向量并确定本地最便宜的东西是行不通的；你最终只会包括B. 基于父级和交替进行决定也不起作用：考虑权重为的E情况1000；现在正确答案是{A,B}，并且它们是相邻的。也许这不应该令人困惑，但坦率地说，我很困惑。

我在课堂测验中遇到了一个问题，要为 Vertex Cover 编写一个非确定性算法。我们和我们的导师讨论了解决方案，他告诉我们水平不确定性不应该太高。它应该是明智的。
我对我应该向非确定性计算机问什么问题感到困惑？

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

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

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