Семинары

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


Расщепление по линейным равенствам

Докладчик: 
Дмитрий Ицыксон
Дата: 
Friday, April 11, 2014 - 17:00
Место: 
ПОМИ, ауд. 203
Аннотация: 

Мы рассматриваем алгоритмы для SAT, которые могут расщепляться по значениям линейных равенств по модулю 2. Например, в одной ветви он может рассматривать случай, что x+y+z=0, а в другой, что x+y+z=1. Будет рассказана экспоненциальная нижняя оценка на время работы всех таких алгоритмов для формул, кодирующих принцип Дирихле. Доказательство этого результата элементарно. Также мы поговорим о связанных с этим алгоритмом системах доказательств (аналог метода резолюций, но работающий с линейными равенствами вместо литералов), для таких систем доказательств мы докажем полиномиальную эквивалентность семантической и синтаксической версии и импликационную полноту.

Летом 2013 года Дима рассказывал нижнюю оценку через коммуникационную сложность. Если останется время, то я расскажу предложенное А. Шенем упрощенное изложение Диминого результата. Доклад не будет зависить от предыдущего Диминого доклада и никаких предварительных знаний не требуется. В конце будет сформулировано несколько открытых вопросов, среди них есть те, которые реально закрыть.

Feedback Vertex Set

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

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

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

Докладчик: 
Александр Куликов
Дата: 
Friday, April 4, 2014 - 18:30
Место: 
ПОМИ, ауд. 203
Аннотация: 

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

Доклад по статье: 
A. Björklund, T. Husfeldt. The Parity of Directed Hamiltonian Cycles. FOCS 2013.

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

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

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

Доклад по статье: 
N. Alon, D. Lokshtanov, S. Saurabh: Fast FAST. ICALP 2009.

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

Доклад по статье: 
D. Lokshtanov, D. Marx, S. Saurabh: Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. SODA 2011.

Pages