“证明确定给定输入G和k是否同时具有大小k和大小独立的集合是NP-Complete。请注意，这是1个问题，而不是2个；如果且仅当答案是yes 如果 G具有这两个子集。”
在我的算法类(class)中我们遇到了这个问题，很多学生都无法解决。这是到目前为止我们所拥有的...
我们知道，集团问题和独立集合问题本身都是NP-Complete。我们也知道，给定一些“证书”，这个问题的验证就在NP中。
问题在于以某种方式将上述问题(包含独立集合和集团)简化为完全由集团或独立集合组成的问题(至少这是我们认为我们需要做的)。我们不知道如何执行此还原操作而不会丢失将还原操作还原为原始形式所需的信息。
最佳答案
提示:通过添加一些顶点，可以减少此问题的CLIQUE。
关于algorithm - 证明NP完整集团+独立设置图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4160978/