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

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