「證明它是NP完全的以確定給定的輸入G和k是否G既有k大小集合又有大小爲k的獨立集合請注意，這是1個問題，而不是2;答案是肯定的當且僅當 G有這兩個子集。「證明NP完全集團+獨立集合圖
在我的算法課程中，我們遇到了這個問題，一大羣學生無法弄清楚。這是我們迄今爲止的...
我們知道集團和獨立集合問題都是NP-Complete。我們也知道，NP中給出了一些「證書」，這個問題的驗證。
這個問題在某種程度上減少了上述問題（它包含獨立集合和派系）或者完全由派系或獨立集合組成的問題（至少這是我們認爲我們需要做的）。我們不知道如何執行這種減少而不會丟失將減少量還原到原始形式所需的信息。
提示：通過添加一些頂點來減少CLIQUE這個問題。
或者：通過添加一些頂點和邊來減少INDEPENDENT-SET到這個問題。 – 2010-11-12 11:10:06
感謝「Moron」和「Rafal Dowgird」的提示！基於這一點，我認爲我有一個解決方案。請糾正我，如果我不正確：
既然我們已經知道集團和獨立集問題是NP完全，我們可以用它作爲證明我們的問題的基礎。讓我們把我們的問題稱爲組合集團獨立集合問題（CCIS）。
假設我們給出了一個圖G，它有一個大小爲k的集團C.通過將k個頂點附加到C中的每個頂點，我們可以將這個圖縮減爲既具有k'大小C'又具有大小k'的獨立集I'的圖G'（讀：G素數）。這種減少發生在自頂點加入起的多項式時間需要O（n * k）個時間（圖中的n個頂點和連接到每個節點的k個頂點）。
注意C = C'和k = k'。
現在假設我們給出了一個圖G'，它具有一個大小爲k'的集團C'和一個大小爲k'的獨立集合I，它被確定爲是真的。因爲我們根本不需要修改圖表來找到一個派系，所以減少派系問題是微不足道的。
從Clique到CCIS的一個更容易的減少是將Clique的輸入圖形添加到它並添加k個孤立的頂點。 （嚴格地說，如果k以二進制形式顯示在輸入中，則添加k個額外頂點相對於輸入的長度是一個指數量的工作，因此您應該檢查k最多是圖中頂點的數量：if k大於該值，產生任何小的「否」實例，例如，單個頂點上的圖形。） – 2014-09-30 00:31:57
另請參見[有關獨立集問題的NP完全性的問題。]（http://stackoverflow.com/questions/2128839/question-about-np-completeness-of-the-independent-set-problem） – Pops 2010-12-11 20:54:03