从顶点盖减少到主导集合

Question

我试图将顶点覆盖（决定）问题减少到主导集合（决定）问题，以证明后者是NP-HARD。在网上研究后，我发现许多文章使用减少，将顶点覆盖问题的输入转换为通过为每个边缘创建三角形来对主导设置问题的输入。 这里是这样的文章之一（见问题7链接）。

我想问的问题是，如果我们将孤立的顶点丢弃到主导集合问题，那么，我们可以很容易地找到一个反例来减少 - 让输入到顶点封面问题是一个图表包含 $ n $ 孤立的节点和参数 $ k= n $ 。现在，主导集合问题的输入将清楚地是一个空图表，参数 $ k= n $ 。现在，有一个大小的顶点封面 $ n $ 。但这不是转换图的主导集（即顶点封面问题的答案是肯定的，但主导集合封面问题的答案是否）。

如何修复减少？有人可以告诉我吗？

Answer 1

如果我正确理解，当Traph $ g=（v，e）$ 具有孤立顶点时，您只有问题。在这种情况下，您可以将 $ g $ 转换为相关图 $ g'=（v \ cup \ {x，y \}，e'）$ 通过添加两个新顶点 $ x $ 和 $ y $ 使 $ x $ 和 $ y $ 通过边缘彼此连接，是 $ x $ 和 $ v $ 之间的彼此顶点之间的边缘。正式： $ e'= e \ cup \ {（x，v）\ mid v \中的v \ cup \ {y \} \} $ 。

如果 $ g $ 承认顶点 - 封面 $ c $ 在大多数 $ k $ ，然后 $ g'$ 承认大多数 $ k + 1 $ ，即 $ c \ cup \ {x} $ 。

如果 $ g'$ 承认顶点封面 $ c $ 大多数 $ k + 1 $ ，然后 $ g $ 承认大多数 $ k $ 。通过注意到 $ c \ setMinus \ {x，y \} $ 必须涵盖中的所有边缘> $ e $ ，并且 $（x，y）\中，确保至少一个 $ x $ 和 $ y $ 在 $ c $ ，即 $ | c \ setminus \ {x，y \} |= | C | - | C \ Cap \ {x，y \} | \ Le | C | - 1 \ Le K $ 。

自 $ g'$ 没有孤立的顶点，您现在可以安全地将其转换为图 $ h $ < / span>主导设置的实例（使用已知的减少）。 通过这种方式，您可以显示 $ G $ 具有大多数 $ k $ <跨越类=“math-container”> $ \ iff $ $ h $ 在大多数 $ k + 1 $ 。