Введение в FPT-алгоритмы

Докладчик: 
Александр Куликов
Дата: 
Sunday, February 2, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

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

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

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