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

Question

这是问题所在。我想知道是否有一个清晰有效的证据：

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

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

一个顶点覆盖它的入射边并支配它的邻居和它自己。

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

Answer 1

有一个非常好的和众所周知的减少：

给定顶点覆盖的实例 (G,k)，构建支配集 (H,k) 的实例，其中 H 取 G，删除所有孤立的顶点，并为每条边 (u,v) 添加一个额外的顶点 x 连接给你和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 是一个顶点覆盖G。

我们有它：当且仅当 H 有一个更小的支配集 k 时，G 有一个更小的顶点覆盖 k。

Answer 2

摘自 ：

CMSC 651 高级算法，讲师 Samir Khuller

Answer 3

我认为第二个问题不是NP。让我们试试下面的算法。

1. Get the original Graph
2. Run any algorithm which checks if a graph is connected or not.
3. mark all used edges of step 2
4. if the graph is connected then return the set of marked edges otherwise there is no such a set.

如果我正确理解了您的问题，那么它不是 NP Complete。