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

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

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