Зауважте, що Макс-Кліка явно в НП. Теорема 20.2 Max-Clique є NP-повною. Потім ми ставимо ребро між двома вузлами, якщо часткові призначення узгоджені. Зауважте, що максимально можливий розмір кліки дорівнює m, тому що немає ребер між будь-якими двома вузлами, які відповідають одному пункту c.

Спеціальні класи графів Зокрема, для планарних графів будь-яка клік може мати щонайбільше чотири вершини, за теоремою Куратовського. Ідеальні графи визначаються тими властивостями, що їх клікове число дорівнює їхньому хроматичному числу, і що ця рівність виконується також у кожному з їхніх індукованих підграфів.

, скорочення залишає графік і параметр без змін: явно результат скорочення є можливим входом для проблеми клік. Крім того, відповідь на обидві проблеми ідентична. Це доводить правильність скорочення і, отже, в NP-повнота кліки-3.

Максимальна кліка клік найбільшого можливого розміру в заданому графіку. Клікове число omega(G) графа G — це кількість вершин у максимальній клікі в G. Число перетину G — це найменша кількість клік, які разом покривають усі ребра G.

Максимальна клік – це клік, який не можна розширити, включивши ще одну сусідню вершину, що означає, що він не є підмножиною більшої кліки. Таким чином, максимальна кліка (тобто кліка найбільшого розміру в даному графі) завжди є максимальною, але зворотне не вірно.

Максимальна відповідна ширина — це параметр ширини графа, який визначається в розкладі розгалуження над набором вершин графа. У цій короткій статті ми доведемо, що проблема обчислення максимальної ширини відповідності є NP-складною.