支配集问题的NP完备性证明

Question

支配集问题的NP完备性证明

np-completereduction

7

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

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

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

一个顶点覆盖它的关联边，而一个支配集则支配它的邻居和自身。

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

- SecureFish

这可能会有所帮助：http://en.wikipedia.org/wiki/Dominating_set#Algorithms_and_computational_complexity - Mahesh Velaga

支配集问题是NP-完全的最小支配集问题，而不仅仅是判断一个图是否存在支配集。为了证明它是NPC问题，需要回答一个简单的是或否问题，所以在一个连通图中使用所有顶点作为支配集是自然的。这不是NPC问题。 - Paul

3个回答

2

摘自：

CMSC 651高级算法，讲师Samir Khuller

- Stav Bodik

-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完全问题。

- Luixv

按照教材CLRS的说法，这应该是NPC问题，:( - SecureFish

CLRS 中的 NPC 是什么问题？ - Luixv

请参考维基百科上的“连通性（图论）”页面，了解贪心连通性算法。 - Luixv

顶点覆盖在CLRS第34章中被认为是NPC问题。 - SecureFish

@Luixv，经过更深思熟虑，我认为你可能是正确的，因为我曾经解决过“使用贪心算法找到最小大小支配集”的问题而感到困惑。 - SecureFish

显示剩余3条评论

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

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

- ian · Accepted Answer

有一个非常不错且广为人知的约简：

给定一个顶点覆盖（G，k）的实例，构建一个支配集（H，k）的实例，其中对于H，您取G，删除所有孤立的顶点，并为每条边（u,v）添加一个连接到u和v的附加顶点x。

首先要认识到G的顶点覆盖是H的支配集：它是G的DS（删除了孤立的顶点），并且新的顶点也被支配。因此，如果G有一个更小的VC，则H有一个更小的DS。

对于反过来的情况，考虑D，H的一个支配集。

请注意，如果D中有一个新的顶点，则我们可以用其两个邻居之一替换它，仍然可以得到一个支配集：它唯一的邻居是两个原始顶点之一，而且它们也是相连的- x可以支配的任何东西也被u或v支配。

因此，我们可以假设D仅包含来自G的顶点。现在，对于G中的每条边（u，v），新顶点x都受D的支配，因此u或v中的一个在D中。但是这意味着D是G的顶点覆盖。

这就是它的全部内容：如果G有一个更小的顶点覆盖，则H有一个更小的支配集，反之亦然。