NP完整性证明了生成树问题

Question

我正在寻找一些提示，这是我的讲师问的问题。

因此，我只是发现这个决策问题是$ sf {np text { - } postive} $：

在图$ g $中，是否有$ g $中的生成树，其中包含$ s = {x_1，x_2， ldots，x_n } $作为叶子的精确集。我发现我们可以证明这是$ sf {np text { - }完整} $，通过将汉密尔顿路径减少到此决策问题。

但是我的教练也在课堂上问我们：

如果是$ sf {np text { - }完整} $，而不是“ $ s $的精确集”，我们会做

“包括整个$ S $以及可能的其他叶子”或“ $ S $的子集”

我认为“ s子集”将是$ sf {np text { - }完整} $，但我无法证明它，我不知道我可以将其减少到什么问题上。至于“包括$ s $ ...”，我认为可以在多项式时间内解决。

Answer 1

简而言之，您的猜测是正确的。出于此答案的目的，让我们称讨论的三个问题如下：

• 平等版本：给定图表$ g =（v，e）$和set $ s subseteq v $，确定$ g $是否具有跨度树$ t $，使得$ t $的叶子集等于$ S $。正如您所说，这是NP的完整性，因为哈密顿路径问题减少了。
• 子集版本：给定的$ g $和上述$ s $，确定$ g $是否具有跨越的树$ t $，以使$ t $中的叶子集是$ s $的子集。
• 超级版本：给定的$ g $和上述$ s $，确定$ g $是否具有跨越的树$ t $，以使$ t $中的一组叶子是$ s $的超集。

为了证明子集版本为NP complete，您仍然可以减少Hamitonian路径问题。尝试修改平等版本的NP完整性的证明。

为了证明可以在多项式时间内解决超集版本，请尝试为存在这种树$ t $的必要条件。

在[SK05]中研究了两个版本（以及有关跨越树的其他一些问题）。但是我想，如果您尝试自己在查看纸张中的证据之前尝试自己解决问题，那就更好了，因为看纸可能是一个很大的破坏者。不幸的是，我在试图找到超级版本的多项式时间算法之前看过了论文！

---

SK05] Mohammad Sohel Rahman和Mohammad Kaykobad。在跨树上的一些有趣问题的复杂性。 信息处理信, ，94（2）：93–97，2005年4月。[[doi] [作者副本]

Answer 2

这些提示还不足以让我解决S超集问题的解决方案 - 尽管这些提示是有帮助和正确的。这是我的思想，让我进入了解决方案。

如果您从g（vs）中删除S中的所有顶点，然后找到带有DFS的生成树T，会发生什么？ V1说，如果G中有任何尚未连接的顶点；这对被删除的至少一个顶点的作用说了什么？它位于目前在生成树上的某个顶点的V1路径中。因此，它不能是叶子（因为叶子没有孩子）。如果没有未连接的节点，则意味着S中的每个顶点都可以是叶子，只要它具有通向生成树的边缘即可。当然，S中仅连接到S中其他顶点的顶点没有与生成树的连接，并且会违反条件。因此，有两种情况需要检查：

1. 如果在从g中删除S并找到一棵生成树后，所有不在s中的节点均已连接
2. 如果S中的每个节点可以直接连接到生成树。