证明定向图诊断为NP-HARD

Question

我有一项家庭作业，我一直在猛击我一段时间，我感谢任何提示。这是关于选择一个已知问题，其证明的NP完整性，并将从该问题构建为以下问题，我将称为DGD（定向图诊断）。

问题

DGD $（v，e，k）$的实例由顶点$ v = i overset {。} { cup} o overset {。} {。} { cup} b $，定向边缘$ e $和一个正整数$ k $。有三种类型的顶点：只有传入边缘$ i $的顶点，仅带有边缘$ o $的顶点和带有传入和传出的边缘$ b $的顶点。再说$ d = o times i $。

现在，问题是我们是否可以用$ d $的最多$ k $元素覆盖所有节点，即

$ qquad displaystyle exists ，s subseteq d，| s | leq k。 forall ，v in V. exists exists exists exists exists exists ，（v_1，v_1，v_2） in S. v_1 to^ to^ to^ to^ to^ to^ to^ * v to^* v_2 $

其中$ a to^* b $意味着有一条从$ a $到$ b $的导向路径。

---

我认为主体设置问题是我应该从中减少的问题，因为这也关心用另一个子集覆盖节点子集。我尝试通过首先为主导集的每个元素创建两个节点，复制所有边缘，然后设置DGD实例的$ k $来创建DGD实例，然后将其设置为DS实例的$ K $。

假设与节点的简单DS-Insance $ 1 $，$ 2 $和$ 3 $以及边缘$（1,2）$和$（1,3）$。这是$ k = 1 $的是肯定的；在这种情况下的主导设置仅包括节点$ 1 $。用刚刚描述的方法还原，这将导致一个DGD实例，其中有两个路径$（1 至2 至1'）$和$（1 至3 至3 至1'）$;要涵盖所有节点，只有一对$（1，1'）$就足够了。如果不是因为DS-Instance的主导集不能在多项式时间内确定，这将是完美的，这是在这里的要求。

我发现，减少边缘和顶点有许多好看的方法，但我的问题是在某种程度上以DS的$ K $表示DGD的$ K $。主导套装似乎是一个合适的问题，但是由于这个问题，我认为也许我应该尝试从没有这样的$ K $的问题中减少？

Answer 1

减少NP完整 设定覆盖 反而。

令$ s_1， dots，s_m subseteq {1， dots，n } $带有$ k in mathbb {n} $ a set Cover的实例。定义DGD的实例$（v，e，k'）$这样：

• $ v = {s_1， dots，s_m，o_1， dots，o_m，e_1， dots，e_n，o } $
• $ e = {（s_i，o_i） mid i = 1， dots，n } cup {（s_i，e_j） mid j in s_i } j = 1， dots，n } $
• $ k'= m + k $

很容易看出，当且仅当给定设置的封面实例具有正面答案时，构造的DGD实例就有一个积极的答案。特别是，必须选择所有$ m $ $对$（s_i，o_i）$，无论如何要覆盖所有$ o_i $;然后，$ m $ $ $对$（s_i，o）$必须覆盖所有$ e_j $，而所选的组件的第一个组件是设定实例的解决方案。如果没有这种选择，则设定实例也没有解决方案。

由于在多项式时间内进行了构建，因此这证明了设置覆盖$ leq_p $ dgd。

---

例如，考虑在 维基百科, ，即$ {1,2,3,4,5 } $并设置$ s = { { {1,2,3 }， {2,4 }， {3,4 }， {4,5 } } $。这转化为以下图：

^[资源]