Семинар по параметризованным и точным алгоритмам,
Осень 2023


Данный семинар посвящен параметризованным алгоритмам. Одно из современных направлений построения эффективных алгоритмов для NP-трудных задач — построение параметризованных FPT-алгоритмов (fixed paramater tractable). Неформально говоря, NP-трудные задачи, это те задачи, для которых неизвестны алгоритмы, работающие «быстро» на любых входных данных. При этом огромное количество задач, возникающих в приложениях, являются NP-трудными. FPT алгоритмы решают сложные задачи «быстро» при условии, что нам известна дополнительная информация о задаче — некоторый параметр ее входа. По сравнению с другими направлениями, такими как приближенные алгоритмы, эвристики и точные алгоритмы, построение FPT алгоритмов — достаточно новое направление, но при этом уже завоевавшее популярность.

Каждый четверг в 13:40 в Zoom 101.
Организаторы: Артур Игнатьев, Юрий Дементьев.

Правила

Сделать хотя бы один доклад на семинаре и посетить хотя бы 60% занятий. Для тех, кто не набрал посещаемость теоретический зачет на пройденные темы.
Запись на доклад

Занятия

  1. 14 сентября. Артур Игнатьев. Слайды.
  2. 21 сентября. Всеволод Васькин. Слайды.
  3. 28 сентября. Вячеслав Безруков. Слайды.
  4. 5 октября. Николай Чухин. Слайды.
  5. 12 октября. Юлия Захватова.
  6. 19 октября. Анастасия Хоробрых. Слайды.
  7. 9 ноября. Марк Пермяков.
  8. 16 ноября. Юрий Дементьев. Слайды.
  9. 23 ноября. Артемий Добышев.
  10. 7 декабря. Николай Чухин. Слайды.

Обязательные темы

  1. Параметризованные алгоритмы, FPT, XP, kernelization. Branching. На примере Vertex Cover (Parameterized Algorithms, страница 12-22, 53-55).
  2. Color coding. \(k\)-path. \(d\)-Clustering (Parameterized Algorithms, страница 103-105, 113-117).
  3. Итеративное сжатие. Feedback Vertex Set in Tournaments. Feedback Vertex Set. (Parameterized Algorithms, страница 77-88)
  4. \(2k\)-ядро для Vertex Cover (Parameterized Algorithms, страница 33-36). Целочисленное линейное программирование. Imbalance problem параметризованная вершинным покрытием (страница 135-139).
  5. Динамическое программирование. Set Cover. Дерево Штейнера (Parameterized Algorithms, страница 129-134).

Дополнительные темы

Parameterized hardness
  1. Daniel Lokshtanov, Daniel Marx, Saket Saurabh. Slightly Superexponential Parameterized Problems.
  2. Daniel Lokshtanov, Dániel Marx, Saket Saurabh. Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal.
Cut problems
  1. Jan Arne Telle, Yngve Villanger. Connecting Terminals and 2-Disjoint Connected Subgraphs.
  2. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Solving the 2-Disjoint Connected Subgraphs Problem Faster Than \(2^n\).
  3. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. On Cutwidth Parameterized by Vertex Cover.
Exact algorithms
  1. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh. Exact Algorithms via Monotone Local Search.
  2. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo. Solving MAX-\(r\)-SAT Above a Tight Lower Bound.
Flow-augmentation
  1. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Directed flow-augmentation.
  2. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Solving hard cut problems via flow-augmentation.
  3. Eun Jung Kim, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström. On weighted graph separation problems and flow-augmentation.
  4. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints.
ML, Algorithmic game theory
  1. Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Dušan Knop, Rolf Niedermeier. Parameterized Algorithms for Finding a Collective Set of Items.
  2. Václav Blažej, Robert Ganian, Dušan Knop, Jan Pokorný, Šimon Schierreich, Kirill Simonov. The Parameterized Complexity of Network Microaggregation.