Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo


Cluster Editing and subexponential algorithms

Speaker: 
Фёдор Фомин
Date: 
Wednesday, March 12, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

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.

Cut-and-Count

Speaker: 
Сергей Копелиович
Date: 
Wednesday, March 5, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

Краткое повторение определений, связанных с 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)$. Нижние оценки для описанных задач.

Древесная ширина

Speaker: 
Роман Колганов
Date: 
Wednesday, February 26, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

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

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

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

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

Алгебраический подход к FPT-алгоримам. Multilinear Detection

Speaker: 
Иван Михайлин
Date: 
Wednesday, February 19, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

Применение MD в FPT-алгоритмах для задач $k$-путь, $k$-дерево, $t$-доминантное множество, $k$-непересекающихся треугольников.

Рандомизированный алгоритм для MD.

Нижняя оценка на размер рабочего кольца в алгебраическом подходе к MD через сведение к коммуникационному протоколу на Set Disjointness. Оптимальности существующих алгоритмов.

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

Speaker: 
Александр Куликов
Date: 
Sunday, February 2, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

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

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

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

Pages