“证明确定给定输入 G 和 k 是 NP 完全的G 拥有这两个子集。”
我们在我的算法课程中遇到了这个问题，一大群学生无法弄清楚。这是我们到目前为止所拥有的...
我们知道集团和独立集问题本身都是 NP-Complete 的。我们也知道这个问题的验证，给定一些“证书”在 NP 中。
问题是以某种方式将上述问题（包含独立集和派系）简化为完全由派系或独立集组成的问题（至少这是我们认为需要做的）。我们不知道如何在不丢失将还原还原到其原始形式所需的信息的情况下执行此还原。
问问题
8360 次
2 回答
6
提示：通过添加一些顶点将 CLIQUE 简化为这个问题。
于 2010-11-12T02:36:49.773 回答
4
感谢“Moron”和“Rafal Dowgird”的提示！基于此，我认为我有一个解决方案。如果我不正确，请纠正我：
由于我们已经知道团和独立集问题是 NP 完全的，我们可以将其用作证明我们的问题的基础。让我们将我们的问题称为组合集团独立集问题（CCIS）。
假设给定一个图 G，它有一个大小为 k 的团 C。我们可以通过将 k 个顶点附加到 C 中的每个顶点，将这个图简化为一个图 G'（读作：G 素数），它具有大小为 k' 的团 C' 和大小为 k' 的独立集 I。这种减少发生在多项式时间，因为添加顶点需要 O(n*k) 时间（图中的 n 个顶点和连接到每个节点的 k 个顶点）。
注意 C=C' 和 k=k'。
现在假设我们得到一个图 G'，它有一个大小为 k' 的团 C' 和大小为 k' 的独立集 I，它被确定为真。由于我们根本不需要修改图来只找到一个集团，因此减少集团问题是微不足道的。
于 2010-11-12T20:49:59.197 回答