Семинар по параметризованным алгоритмам

Общая информация
ЛекторА. С. Куликов
Семестрвесна 2014
Дата начала12.02.2014
Количество пар12
Язык курсарусский
Аннотация

Параметризованные алгоритмы — молодая область Computer Science с множеством интересных результатов и открытых задач. Основным объектом её исследования являются оценки на время работы алгоритмов относительно не только размера входа, но также и некоторого дополнительного параметра. Например, асимптотически самый быстрый известный алгоритм для NP-трудной задачи о вершинном покрытии имеет время работы $ O^*(c^n) $, где $ n $ — количество вершин графа, а $ 1<c<2 $ — константа. Поскольку время работы экспоненциально, с ростом $ n $ такой алгоритм довольно быстро становится непрактичным. В то же время довольно просто придумать алгоритм, который за время $ O^*(2^k) $ проверят, есть ли в графе вершинное покрытие размера не более $ k $. Такой алгоритм называется fixed-parameter tractable (FPT). Как видно, при небольшом $ k $ данный алгоритм вполне может быть применён на практике. Формально, алгоритм называется fixed-parameter tractable, если его время растёт как $ f(k)n^{O(1)} $. Другими словами, при фиксированном значении параметра $ k $ время работы алгоритма растёт полиномиально. В примере выше в качестве параметра выступает размер выхода, но есть и много других естественных параметризаций. Интерес представляют параметризации, при которых сложные входы задач по-прежнему имеют небольшое значение параметра.

В курсе будет дан обзор известных результатов и открытых задач данной области. Заинтересованным студентам будут выданы статьи/главы книг для выступления на семинаре.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение (Александр Куликов)
(12.02.2014 - 18:00 - 19:35)

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

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

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

2. Алгебраический подход к FPT-алгоримам. Multilinear Detection (Иван Михайлин)
(19.02.2014 - 18:00 - 19:35)

Применение MD в FPT-алгоритмах для задач $ k $-путь, $ k $-дерево, $ t $-доминантное множество, $ k $-непересекающихся треугольников. Рандомизированный алгоритм для MD. Нижняя оценка на размер рабочего кольца в алгебраическом подходе к MD через сведение к коммуникационному протоколу на Set Disjointness. Оптимальности существующих алгоритмов.
3. Древесная ширина (Роман Колганов)
(26.02.2014 - 18:00 - 19:35)

Многие NP-трудные задачи можно эффективно решать на деревьях с помощью динамического программирования. Произвольный граф можно в некотором смысле "уложить" на дерево, получив так называемую древесную декомпозицию. При этом древесная ширина - это параметр, в некотором смысле определяющий, насколько хорошо граф "укладывается" на дерево. Эта техника позволяет перенести идею динамического программирования по деревьям на произвольные графы.

Применение динамического программирования с использованием древесной декомпозиции графа для решения NP-трудных задач, в частности, максимального взвешенного независимого множества, минимального доминирующего множества, дерева Штейнера.

Алгоритм поиска древесной ширины и построения почти оптимальной древесной декомпозиции.

Несколько естественных задач, эквивалентных построению древесной декомпозиции, например, поимка грабителя в графе минимальным числом полицейских. Классы графов, которые имеют небольшую древесную ширину: графы с маленькой максимальной степенью вершин, планарные графы. Эффективные алгоритмы для таких графов, например, вершинное покрытие размера $ k $ планарного графа за время $ 2^{\mathcal{O}(\sqrt{k})} \cdot n^{\mathcal{O}(1)} $.

4. Cut-and-Count (Сергей Копелиович)
(05.03.2014 - 18:00 - 19:35)

Краткое повторение определений, связанных с treewidth (treewidth, nice tree). Сut & count — общий принцип. Дерево Штейнера (Shteiner Tree) на $ |V| = n $, $ |E| = m $ графе для множества $ T $. Решения для $ |T| = k $ за $ 3^k \cdot m $, использование cut & count, решение за $ 3^{tw} \cdot \operatorname{poly}(n) $. Покрытие ориентированными циклами (Directed Cycle Cover): решения за $ 3^n $ и $ 2^n \cdot \operatorname{poly}(n) $, использование cut & count, решение за $ 6^{tw} \cdot \operatorname{poly}(n) $. Нижние оценки для описанных задач.
5. Cluster Editing and subexponential algorithms (Фёдор Фомин)
(12.03.2014 - 18:00 - 19:35)

We discuss (a bit unusual) behavior of certain NP-complete problems admitting subexponential algorithms. For example, the $ p $-Clustering problem is to decide for a given $ n $-vertex graph $ G $ and integers $ k $ and $ p $, if $ G $ can be turned into a $ p $-cluster (disjoint union of $ p $ cliques) by at most $ k $ edge modifications (adding/deleteling edges). We give a subexponential algorithm solving this problem in time $ O(exp((\sqrt{qp}) +n +m) $. On the other hand, there are strong arguments showing that most of NP-complete problems cannot be solved in subexponential time. While existence of subexponential time algorithms does not resolve P vs NP question, it shows an interesting diversity of the world of intractable problems.
6. Strong ETH and lower bounds for treewidth (Евгений Краско)
(26.03.2014 - 18:00 - 19:30)

SETH — гипотеза, утверждающая, что $ \forall \epsilon > 0 $ задачу SAT нельзя решить за время $ O^*((2-\epsilon)^{n}) $, где $ n $ — количество переменных. Так как SAT можно свести к другим $ NP $-трудным задачам, из SETH следуют и некоторые нижние оценки на время решения этих задач.

Оказывается, что из SETH можно вывести и нижние оценки на время решения некоторых задач, зависящих от параметра. Например, из SETH следует, что задачу Dominating Set $ \forall \epsilon > 0 $ нельзя решить за время $ O^*((3-\epsilon)^{tw(G)}) $ ($ tw(G) $ — древесная ширина графа $ G $). Для доказательства подобных фактов можно, например, найти такое сведение SAT к нужной задаче, которое бы приводило к инстансам задачи с небольшим значением параметра. Доклад посвящён таким сведениям для нескольких известных задач, параметризованных древесной шириной. Выведенные таким образом нижние оценки уже достигнуты существующими алгоритмами. Отсюда следует, что если эти алгоритмы удастся улучшить, то и для SAT будет немедленно получен более быстрый алгоритм.
7. Цветовое и хроматическое кодирование (Павел Чуприков)
(02.04.2014 - 18:00 - 19:30)

Поиск ориентриованного $ k $-цикла за среднее время $ 2^{O(k)}V^\omega $, и $ 2^{O(k)}V^\omega \log V $ — в худшем случае. Поиск взвешенного множества дуг обратной связи в турнире за $ 2^{O(\sqrt{k}\log k)} + n^{O(1)} $ среднее и худшее время.
8. Feedback Vertex Set (Кирилл Елагин)
(09.04.2014 - 18:00 - 19:30)

Мы познакомимся с техникой итеративного сжатия на примере задачи о поиске разрывающего множества вершин в турнире. Затем изучим некоторые продвинутые методы кернелизации и получим с помощью них квадратичное ядро для задачи о разрывающем множестве в произвольном неориентированном графе.
9. Задача поиска кратчайшего цикла в графе через выбранные вершины (Р. Демидов)
(23.04.2014 - 18:00 - 19:30)

В своем докладе я расскажу вероятностный с односторонней ошибкой $ 2^k\operatorname{poly}(n) $ алгоритм Бьорклунда для задачи нахождения $ k $-цикла в неориентированном графе (т.е цикла, проходящего через $ k $ заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.
10. Feedback Vertex Set Problem (Сергей Савинов)
(14.05.2014 - 18:00 - 19:30)

В докладе рассмотрим FPT алгоритм для задачи Feedback Vertex Set Problem в ориентированном графе. Для этого построим сведение к задаче поиска Skew Separator problem, для которой предоставим решение. Сложность алгоритма исходной задачи $ 4^kk!n^{O(1)} $.
11. Representanive sets (Михаил Слабодкин)
(21.05.2014 - 18:00 - 19:30)

Эффективное нахождение $ q $-репрезентативных семейств для линейных матроидов. Решение задач $ k $-path и $ k $-cycle для ориентированных и неориентированных графов с помощью репрезентативных семейств регулярных матроидов.
Ваша оценка: Пусто Средняя: 3 (2 голосов)
Share |