Кернелизация, построение ядер. КГТ-разложением(разложение короной, Crown Decomposition), лемма о подсолнухах(Sunflower lemma). Построение ядер с помощью линейного программирования.

1. Ядро размера $3k$ для Vertex Cover (КГТ-разложение)
2. Ядро для задачи о максимальной выполнимости: $k$ переменных, $2k$ клозов (КГТ-разложение)
3. Ядро для $d$-Hitting Set c $d! k^d$ множествами
4. Ядро с $2k$ вершинами для задачи о вершинном покрытии (линейное программирование)