从最大独立集合减少到支配集合以证明支配集合是NP完全的

Question

我知道从顶点覆盖减少到支配集合。

但是，我看到是否可以从最大独立集问题直接减少到支配集问题，以证明后一个NP完全。

有谁知道这是否已经完成？我无法在网上找到任何东西。

我希望能找到像沿证明的东西线：

如果有一个支配集大小为k - >还有一个最大独立集大小为k。

AND

如果有一个最大独立集大小为k的 - >然后有一个控制集大小为k。

Answer 1

是的，你可以从最大独立集问题直接减少到支配集问题 - 但不是那么直接，你需要以下面的方式构造另一个图。然后我们可以证明，如果新图有一个与k有关的一定大小的支配集，那么如果原始图具有独立的一组大小k。构造是多项式的。

给定图G = (V, E)我们可以在E构造另一个图表G' = (V', E')其中对于每个边缘e_k = (v_i, v_j)，我们添加一个顶点v_{e_k}和两个边缘(v_i, v_{e_k})和(v_{e_k}, v_j)。

我们可以证明G有一个独立的尺寸集合k iff G'具有支配尺寸集合|V|-k。

（=>）假设我是一个大小 - k独立设置的G，然后V-I必须是G'一个大小 - (|V|-k)支配集。由于I中没有连接顶点对，因此I中的每个顶点都连接到V-I中的某个顶点。此外，每个新添加的顶点也连接到V-I中的某些顶点。

（< =）假设D是一个大小 - (|V|-k)独立设置的G'，那么我们可以安全地假设在D所有顶点是在V（因为如果D包含添加的顶点，我们可以通过与其相邻的一个替换它顶点在V并且仍然具有相同大小的主导集合）。

我们要求V-D是G一个尺寸 - k独立设置，并通过矛盾证明这一点：假设V-D是不是独立的，包含一对顶点v_i和v_j和边缘e_k = (v_i, v_j)是E的。然后，在G'中，增加的顶点v_{e_k}需要由v_i或v_j支配，即v_i和v_j中的至少一个在D中。矛盾。因此V-D是一个大小-k独立设置在G。

结合这两个方向，你得到你想要的。