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

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

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

Минимальный размер кликового покрытия графа — наименьшее число ${\displaystyle k}$, для которого кликовое покрытие существует.

Связанная задача нахождения числа пересечения рассматривает множества клик, включающих все рёбра заданного графа; эта задача также NP-полна.