Прошел семинар лаборатории: "Алгоритмы на графах малой древесной ширины"

Прошел семинар лаборатории теоретической информатики 30 октября 2025 года.

МЛ ТИ

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

На семинаре рассмотрели следующее:

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

Запись семинара представлена ниже