irt*_*d88 7 algorithm computer-science np-complete clique-problem
"证明给定输入G和k是NP是完全的,G是否同时具有大小为k的集团和一个独立的大小为k的集合.请注意,这是1个问题,而不是2;答案是肯定的,当且仅当 G有这两个子集."
我的算法课程中遇到了这个问题,一大群学生无法弄明白.这是我们到目前为止所拥有的......
我们知道,集团和独立集合问题本身就是NP-Complete.我们也知道,对于这个问题的验证,给出一些"证书"是在NP中.
问题是以某种方式将上述问题(包含独立集合和集团)的问题简化为完全由集团或独立集合组成的问题(至少我们认为我们需要这样做).我们不知道如何在不丢失将减少量减少回原始形式所需的信息的情况下执行此减少.
感谢“白痴”和“拉法尔·道格德”的提示！基于此，我想我已经找到了解决方案。如果我不正确，请纠正我：
由于我们已经知道派系和独立集问题是 NP 完全问题，因此我们可以用它作为证明我们的问题的基础。我们将我们的问题称为组合派独立集问题 (CCIS)。
假设我们有一个图 G，它有一个大小为 k 的团 C。我们可以通过将 k 个顶点附加到 C 中的每个顶点，将该图简化为图 G'（读作：G prime），该图具有大小为 k' 的团 C' 和大小为 k' 的独立集 I。这种减少发生在多项式时间，因为添加顶点需要 O(n*k) 时间（图中的 n 个顶点和附加到每个节点的 k 个顶点）。
请注意，C=C' 且 k=k'。
现在假设我们给出一个图 G'，它有一个大小为 k' 的集团 C' 和大小为 k' 的独立集 I，并且被确定为 true。减少派系问题是微不足道的，因为我们根本不需要修改图来只找到一个派系。