Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа на клик. Является NP-полной; входит в список из 21 NP-полных задач Карпа.
Если дано разбиение вершин на множеств, то можно за полиномиальное время определить, что каждое множество образует клику так, что задача принадлежит классу NP. NP-полнота задачи о кликовом покрытии следует из сведения её к задаче раскраски графа: разложение графа на клик соответствует нахождению разложения вершин дополнения на независимых множеств (каждому из этих множеств можно назначить один цвет, что даст -раскраску).
Минимальный размер кликового покрытия графа — наименьшее число , для которого кликовое покрытие существует.
Связанная задача нахождения числа пересечения рассматривает множества клик, включающих все рёбра заданного графа; эта задача также NP-полна.
Примечания
Литература
A1.2: GT19, стр. 194.
Категория:NP-полные задачи Категория:Вычислительные задачи теории графов