证明对于给定输入G和k，确定G是否同时具有大小为k的团和大小为k的独立集合是NP完全问题。请注意，这是一个问题而不是两个问题；当且仅当G具有这两个子集时，答案为是。在算法课程中，我们被给予了这个问题，但很多学生都无法解决它。我们已经知道独立集和团问题本身就是NP完全问题。我们还知道，如果给定某些“证书”，则该问题的验证在NP中进行。问题需要在以上既包含独立集又包含团的问题上执行约减，使其转化为完全由团或者独立集组成的问题（至少我们认为是这样）。我们不知道如何进行此约减，而不会丢失还原回原始形式所需的信息。
证明团和独立集问题在图中的NP完备性
12
- irtemed88
1
另请参见关于独立集合问题NP完备性的问题。 - Pops
2个回答
7
提示：通过添加一些顶点，将CLIQUE问题简化为此问题。
- Aryabhatta
1
4另外，可以通过添加一些顶点和边将独立集问题归约到此问题。 - Rafał Dowgird
5
感谢“Moron”和“Rafal Dowgird”的提示！基于此，我认为我已经找到了一个解决方案。如果我错了，请纠正我：
由于我们已经知道团与独立集问题是NP完全问题，因此我们可以将其作为证明我们问题的基础。让我们称之为组合团独立集问题（CCIS）。
假设我们有一个图G，其中有一个大小为k的团C。我们可以将此图缩减为一个图G'（读作G prime），该图具有大小为k'的团C'和大小为k'的独立集I，方法是将k个顶点附加到C中的每个顶点。由于添加顶点需要O（n * k）时间（图中的n个顶点和每个节点附加的k个顶点），因此此缩减发生在多项式时间内。
请注意，C = C'且k = k'。
现在假设我们有一个图G'，其中有一个大小为k'且确定为真的团C'和大小为k'的独立集I。对于寻找团，缩减过程很简单，因为我们根本不需要修改图形。
由于我们已经知道团与独立集问题是NP完全问题，因此我们可以将其作为证明我们问题的基础。让我们称之为组合团独立集问题（CCIS）。
假设我们有一个图G，其中有一个大小为k的团C。我们可以将此图缩减为一个图G'（读作G prime），该图具有大小为k'的团C'和大小为k'的独立集I，方法是将k个顶点附加到C中的每个顶点。由于添加顶点需要O（n * k）时间（图中的n个顶点和每个节点附加的k个顶点），因此此缩减发生在多项式时间内。
请注意，C = C'且k = k'。
现在假设我们有一个图G'，其中有一个大小为k'且确定为真的团C'和大小为k'的独立集I。对于寻找团，缩减过程很简单，因为我们根本不需要修改图形。
- irtemed88
1
2从Clique到CCIS的更简单的约化是将Clique的输入图形添加k个孤立顶点。 （严格来说，如果k以二进制形式出现在输入中，则相对于输入长度添加k个额外顶点是指数级的工作量。因此，您应该检查k是否最多为图中的顶点数：如果k大于该值，请生成任何小的“否”实例，例如单个顶点上的图形。） - David Richerby
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接