Seminars

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



Задача редактирования графа до графа с заданными степенями

Speaker: 
Пётр Головач
Date: 
Thursday, September 18, 2014 - 18:00
Place: 
ПОМИ РАН, Мраморный зал
Abstract: 

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph $G$, non-negative integers $d,k$ and a function $\delta \colon V(G) \to \{1,...,d\}$, whether it is possible to obtain a connected graph $G’$ from $G$ such that the degree of $v$ is $\delta(v)$ for any vertex $v$ by at most $k$ edge editing operations. As the problem is NP-complete even if $\delta(v)=2$, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by $d+k$. For the special case $\delta(v)=d$, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. We also investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. In particular, we obtain polynomial-time algorithms for the Edge Editing to an Eulerian Graph problem and its directed variant.



2 11/23 - приближение для задачи о кратчайшей надстроке

Speaker: 
Евгений Служаев
Date: 
Monday, September 15, 2014 - 18:30
Place: 
Аудитория 203
Abstract: 

Будет рассказано об алгоритме Марчина Мухи и получено 2 11/23 - приближение для задачи о кратчайшей надстроке, которое является наилучшим из известных на сегодняшний день приближений для этой задачи.



Приближённые алгоритмы для Feedback vertex set

Speaker: 
Всеволод Опарин
Date: 
Monday, July 21, 2014 - 18:00
Place: 
ПОМИ, ауд. 203
Abstract: 

Я расскажу про два подхода при приближенном решении задачи Feedback vertex set. Первый подход является комбинаторным, основывается на технике расслоения и дает 2-приближение. Второй метод называется прямодвойственным (primal-dual), дает 4 log_2 n - приближение. Мы формулируем задачу в терминах LP, находим ей дуальную и на основе дуальной строим эффективный алгоритм.



О сложности задачи выполнимости схемы

Speaker: 
Иван Михайлин
Date: 
Thursday, June 19, 2014 - 13:00
Place: 
ПОМИ, ауд. 203
Abstract: 

В докладе будет доказано, что из разумных предположений на схемную сложность NP-полных задач следует, что любой полиномиальный алгоритм с односторонней ошибкой для Circuit-SAT будет давать очень маленькую вероятность успеха.


Pages