Seminars

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



Feedback Vertex Set

Speaker: 
Кирилл Елагин
Date: 
Wednesday, April 9, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

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



Чётность гамильтоновых циклов

Speaker: 
Александр Куликов
Date: 
Friday, April 4, 2014 - 18:30
Place: 
ПОМИ, ауд. 203
Abstract: 

Будет рассказан недавний алгоритм подсчёта чётности гамильтновых циклов в ориентированных графах быстрее полного перебора (напомним, что мы на данный момент не умеем проверять, есть ли в орграфе гамильтонов цикл за 1,99^n, а вот чётность числа таких циклов, как выясняется, находить умеем).



Цветовое и хроматическое кодирование

Speaker: 
Павел Чуприков
Date: 
Wednesday, April 2, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

Поиск ориентированного $k$-цикла за среднее время $2^{O(k)}V^\omega$, и $2^{O(k)}V^\omega \log V$ — в худшем случае. Поиск взвешенного множества дуг обратной связи в турнире за $2^{O(\sqrt{k}\log k)} + n^{O(1)}$ среднее и худшее время.



Strong ETH and lower bounds for treewidth

Speaker: 
Евгений Краско
Date: 
Wednesday, March 26, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

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

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.


Pages