我知道从顶点覆盖到支配集的减少。
但是，我正在查看是否可以将最大独立集问题直接简化为支配集问题，以证明后者是 NP 完全的。
有谁知道这是否已经完成？我在网上找不到任何东西。
我希望找到类似证明的东西：
如果有一个大小为 k 的支配集 -> 有一个大小为 k 的最大独立集。
和
如果存在大小为 k 的最大独立集 -> 则存在大小为 k 的支配集。
问问题
1961 次
1 回答
0
是的，您可以从最大独立集问题直接减少到支配集问题 - 但不是那么直截了当，您需要以下列方式构造另一个图。然后我们可以证明，如果原始图有一个独立的大小集，k当且仅当新图有一个与 k 相关的某个大小的支配集。构造是多项式的。
给定一个图G = (V, E) ，我们可以构造另一个图G' = (V', E')，其中对于 中的每条边e_k = (v_i, v_j)，E我们添加一个顶点v_{e_k}和两条边(v_i, v_{e_k})和(v_{e_k}, v_j)。
我们可以证明G有一个独立的大小集k当且仅当G'有一个支配集的大小|V|-k。
(=>) 假设 I 是 的大小k无关集G，则V-I必须是 的大小(|V|-k)支配集G'。由于 in 中没有连接的顶点对I，因此 in 中的每个顶点都与 inI中的某个顶点相连V-I。此外，每个新添加的顶点也连接到 中的一些顶点V-I。
(<=) 假设D是一个与大小(|V|-k)无关的集合G'，那么我们可以安全地假设 in 的所有顶点D都在V（因为如果D包含一个添加的顶点，我们可以用它的一个相邻顶点来替换它，V并且仍然有一个支配集合大小相同）。
我们声称V-D是一个与大小k无关的集合，G并通过反证法证明：假设V-D不独立并且包含一对顶点v_i并且v_j边e_k = (v_i, v_j)在 中E。那么在G'所添加的顶点中v_{e_k}需要以v_ior为主v_j，即至少是v_i和v_j中的一个D。矛盾。因此V-D是一个与大小k无关的集合G。
结合这两个方向，你会得到你想要的。
于 2013-06-15T07:29:53.587 回答