Определение параметризованной задачи и FPT-алгоритма. Сравнение функций \( 2^kn \) и \( n^{k+1} \). Примеры FPT-задач: вершинное покрытие размера \( k \), \( k \)-путь, \( k \) непересекающихся треугольников. Примеры трудных задач: клика, независимое множество, доминирующее множество.

Ядра (кернелизация). Эквивалентность существования FPT-алгоритма и существования ядра. Простейшие примеры ядер: ядро размера \( k(k+1) \) для вершинного покрытия, ядро размера \( k^2 \) для покрытия точек прямыми.

Примеры FPT-алгоритмов. Color coding и \( k \)-путь. Итеративное сжатие и задача об удалении нечётных циклов.