algorithm - 证明最小循环覆盖的不可近似性

Question

考虑循环覆盖问题:给定图 G，我们寻找一组循环 C，使得 V(G) 的所有顶点至少在 C 的一个循环中，并且 C 中的循环数最少。

我的任务是证明这个问题不允许绝对近似，即，不可能有算法 H 使得对于问题的所有实例 I，H(I) <= OPT(I) + k，其中OPT(I) 是 I 的最优值，k 是一个大于或等于 1 的数。通常的技术是证明如果这个算法存在，我们可以在多项式时间内解决一些 NP-hard 问题。

有谁知道哪个问题可以解决这个问题？

Answer 1

假设有一个算法H这样就有一个正整数k这样对于每个图 G , H(G)<=OPT(G)+k成立，其中 OPT(G)表示覆盖 G 的所有节点所需的最小循环数和 H 的运行时间在 n 中多项式有界, 其中n是G的节点数.

给定任何图G , 创建图表 G'其中包括 k+1 G 的同构副本;请注意 G' 中的节点数是(k+1)n ，它在 n 中是多项式有界的.可能会出现以下两种情况:

1. 如果 G包含哈密顿循环，则 OPT(G')=k+1和 H(G')<=OPT(G')+k=k+1+k=2k+1 .

2. 如果 G不包含哈密顿循环，则 OPT(G')>=2k+2>2k+1因此 H(G')>2k+1 .

总的来说，H可用于决定在 n 中多项式有界的运行时绑定(bind)是否G包含哈密顿循环；然而，作为决定是否G有一个哈密顿循环是一个NP - 完整的决策问题，这是不可能的，除非P=NP持有。

注意:这种方法称为“差距创造”，因为实例的转换方式使得目标值存在差距

1. yes-instances 的最优解；
2. yes-instances 的次优解决方案和 no-instances 的可行解决方案。