分团覆盖问题

在计算复杂度理论内，找一个最小的分团覆盖（clique cover）是一个图论的NP完全问题。这问题属于卡普的二十一个NP-完全问题之一，由卡普在1972年的论文"Reducibility Among Combinatorial Problems"证明为NP完全^[1]。

分团覆盖问题（有时叫做分成分团，partition into cliques）是问一个图里面的所有点可否分成k个分团。一旦给定了这个图该怎么分成k个分团，我们可以在多项式时间里面检证这个答案是否正确，因此我们可以知道这个问题属于NP。

分团覆盖问题是NP完全这件事情，可以借由将此问题从k-图着色问题（GRAPH k-COLOURABILITY）归约出来而得证^[2]。要推出这个结果，首先我们将一个k-图着色问题的输入图G转成其补图G'。那么，求出G' 怎么分出k个分团这问题就等同于求出G怎么分出k个独立集；我们能将每个独立集设立一个颜色来得到k个颜色，并且保证G内所有相同颜色的点不会互相连接。因此，解出G' 的分团问题，即是解出G的着色问题。因为我们已知k-着色问题是NP完全问题，所以我们能借由将所有NP的问题先归约为k-着色问题，再归约为分团覆盖问题，而将所有NP完全问题归约成分团覆盖问题。故分团覆盖问题是NP完全问题。

相关的问题分团边覆盖则是考虑是否存在分团的集合能包含图中所有的边（edge）。这个问题也一样是NP完全问题。