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

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

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

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

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