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

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

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

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

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

Литература

• Richard Karp. Proceedings of a Symposium on the Complexity of Computer Computations / R. E. Miller, J. W. Thatcher. — Plenum Press, 1972. — С. 85—103.
  • P. M. Карп. Кибернетический сборник (новая серия) / О. Б. Лупанов. — М.: «Мир», 1975. — С. 16—38.
• Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5. A1.2: GT19, стр. 194.
  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М., 1982.