Задача про клікове покриття

Задача про клікове покриття — обчислювальна задача, яка полягає у визначенні можливості розбити вершини графу на ${\displaystyle k}$ клік. Є NP-повною; входить до числа 21 NP-повних задач Карпа.

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

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

Пов'язана задача знаходження числа перетинів розглядає множини клік, що включають усі ребра даного графу; ця задача також NP-повна.

Примітки

1. Карп, 1975, с. 16—38.

Література

• Richard Karp. [1] / R. E. Miller, J. W. Thatcher. — Plenum Press, 1972. — С. 85—103. з джерела 29 червня 2011
  • 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. — . A1.2: GT19, стр. 194.
  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М. : «Мир», 1982.