Семинары

Рассылка: https://groups.google.com/forum/#!forum/spb-algo



Strong ETH and lower bounds for treewidth

Докладчик: 
Евгений Краско
Дата: 
Wednesday, March 26, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

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 будет немедленно получен более быстрый алгоритм.



Cluster Editing and subexponential algorithms

Докладчик: 
Фёдор Фомин
Дата: 
Wednesday, March 12, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

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

Докладчик: 
Сергей Копелиович
Дата: 
Wednesday, March 5, 2014 - 18:00
Место: 
ПОМИ, Мраморный зал
Аннотация: 

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



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

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

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

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

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

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



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

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

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

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

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


Pages