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

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

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