np-complete - 证明支配集是NP完全的

Question

这是问题。我想知道是否有一个清晰有效的证明:

顶点覆盖:输入无向G，整数k>0。是否存在的子集
顶点S，| S | <= k，覆盖所有边？

支配集:输入无向G，整数k> 0。
顶点S，| S | <= k，该顶点支配所有顶点？

顶点覆盖了它的入射边缘，并支配了它的邻居和自身。

假设VC是NPC，则证明DS是NPC。

Answer 1

有一个相当不错的众所周知的减少量:

给定Vertex Cover的一个实例(G，k)，构建一个支配集(H，k)的实例，其中对于H，您取G，删除所有孤立的顶点，并为每个边(u，v)添加一个附加的顶点x到u和v。

首先要认识到G的顶点覆盖是H的主导集:它是G的DS(在除去孤立的顶点之后)，并且新顶点也被主导。因此，如果G的VC小于k，则H的DS小于k。

相反，考虑D，H的支配集。

请注意，如果新顶点之一在D中，我们可以用它的两个相邻顶点之一替换它，并仍然得到一个主导集合:它只有两个相邻顶点是两个原始顶点，并且它们也都相连-x可以主导的一切都是也由u或v主导。

因此，我们可以假设D仅包含来自G的顶点。现在，对于G中的每个边(u，v)，新顶点x都由D主导，因此u或v都在D中。但这意味着D是D的顶点覆盖G。

就是这样:当且仅当H的控制集的k较小时，G的顶点覆盖度才更小。