多项式时间算法

Question

3

有什么多项式时间算法可以找到[V / 2]个顶点，这些顶点在任意无向图中至少占据四分之三（3/4）的边缘？

请帮忙。

- Aakash

不存在这样的子集是有保障的。 - Dr. belisarius

@belisarius 你有反例吗？我认为它肯定存在且很容易找到，但我的逻辑可能有误。 - bnaul

也许我理解有误，但如果你有一个项链型图V/2个顶点，约占一半的边。 - Dr. belisarius

@belisarius 在二分图中选择任意一个分区即可涵盖所有边。由于循环图要么是二分图，要么只有一条边与二分图相差一步，因此通过在链中选择V/2个交替项，我们只会错过一条边。 - Yonatan N

@Yonatan 谢谢你的回答。我的英语理解能力并不总是达到要求。至少我克制住了回答的冲动 :) - Dr. belisarius

3个回答

1

仔细想想，这似乎不合理。不过我仍然认为贪心算法是可行的；如果你选择至少具有平均度数的顶点，那么最终你应该能够获得大部分总边数。但是我对证明还不确定。

- bnaul

1

我认为你对顶点覆盖问题的解释是错误的（要么我误解了你）。近似算法可能会给出比必要顶点数量多一倍的结果，而不是少一半（否则就会有超最优解！） - Yonatan N

嗯，使用最贪心的算法：删除具有最大边数的顶点以及这些边。重复[V/2]次。 - comingstorm

1

这里有一个证明它存在的方法：

考虑随机选择一半顶点的算法。对于任何给定的边，其两个端点中至少有一个被选择的概率为3/4，因此覆盖的边数的期望值为3|E|/4。因此，根据概率方法，必须至少存在一种使用仅1/2的顶点覆盖>= 3|E|/4条边的方法。非确定性算法随即而来。

基于此构建一个确定性算法是一种去随机化的练习（尝试使用条件期望法）。

- Yonatan N

我了解概率方法。你能否以数学上具有说服力的证明来更详细地解释确定性算法呢？非常感谢。 - Aakash

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jason · Accepted Answer

有这个算法吗？我怀疑没有，但说实话我不知道；顶点覆盖是NP完全问题，而这个问题很接近（我们正在询问 G 是否具有大小为至多 |V| / 2 的顶点覆盖，可以覆盖四分之三的边。）

显然，尝试使用贪心算法，首先选择度数最高的顶点。