Семинар МЛ ТИ "Алгоритмы на графах малой древесной ширины"

Дата: 30 октября 2025 г., 18:10 - 19:30

Докладчик: Кауркин Владимир, стажер-исследователь международной лаборатории теоретической информатики

Аннотация: Некоторые задачи, NP-полные в общем случае, можно эффективно решать на специальных классах графов: например, из курса алгоритмов известно, что наибольшее независимое множество на деревьях можно найти за линейное время простым динамическим программированием. Оказывается, что этот результат можно обобщить на графы, «близкие к деревьям» — с малой древесной шириной (treewidth). Обсудим на примерах, как можно применять динамическое программирование к графам общего вида с ограниченной древесной шириной. Центральный результат, доказательство которого планируется обсудить — теорема Курселя: любые свойства графов, формулируемые в MSO2, на графах с константной древесной шириной проверяются за время, линейное по размеру графа (при этом зависимость от размера формулы и древесной ширины может быть сверхэкспоненциальной). Если останется время, обсудим FPT-алгоритм для приближенного вычисления древесной ширины (сама по себе задача точного нахождения древесной ширины данного графа NP-полна).

Приглашаем всех заинтересованных!

Место проведения:

Очно: АУК Покровский бульвар, R204

Онлайн: Zoom

Идентификатор конференции: 841 2388 6260
Код доступа: 067656