分團覆蓋問題 在計算複雜度理論內找一個最小的分團覆蓋clique cover是一個圖論的NP完全問題這問題屬於卡普的二十一個NP完全問題之一由卡普在年的論文Reducibility Among Combinatorial Problems證明為NP完全 分團覆蓋問題有時叫做分成分團partition into cliques是問一個圖裡面的所有點可否分成k個分團一旦給定了這個圖該怎麼分成k個分團我們可以在多項式時間裡面檢證這個答案是否正確因此我們可以知道這個問題屬於NP 分團覆蓋問題是NP完全這件事情可以藉由將此問題從k圖著色問題GRAPH kCOLOURABILITY歸約出來而得證要推出這個結果首先我們將一個k圖著色問題的輸入圖G轉成其補圖G那麼求出G 怎麼分出k個分團這問題就等同於求出G怎麼分出k個獨立集我們能將每個獨立集設立一個顏色來得到k個顏色並且保證G內所有相同顏色的點不會互相連接因此解出G 的分團問題即是解出G的著色問題因為我們已知k著色問題是NP完全問題所以我們能藉由將所有NP的問題先歸約為k著色問題再歸約為分團覆蓋問題而將所有NP完全問題歸約成分團覆蓋問題故分團覆蓋問題是NP完全問題 相關的問題分團邊覆蓋則是考慮是否存在分團的集合能包含圖中所有的邊edge這個問題也一樣是NP完全問題