Задача о кликовом покрытии

Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа на $k$ клик. Является NP-полной; входит в список из 21 NP-полных задач Карпа Шаблон:Sfn.

Если дано разбиение вершин на $k$ множеств, то можно за полиномиальное время определить, что каждое множество образует клику так, что задача принадлежит классу NP. NP-полнота задачи о кликовом покрытии следует из сведения её к задаче раскраски графа: разложение графа $G$ на $k$ клик соответствует нахождению разложения вершин дополнения $G^{'}$ на $k$ независимых множеств (каждому из этих множеств можно назначить один цвет, что даст $k$ -раскраску).