Структурные параметры графов

Задачи о длинном пути (Longest Path), независимом множестве (Independent Set) или раскраске графа в минимальное число цветов (Chromatic Number) — примеры известных NP-трудных задач. Но что именно делает их такими трудными? Ведь найти самый длинный путь в дереве, найти максимальное независимое множество в двудольном графе или раскрасить набор отрезков на прямой так, чтобы одноцветные отрезки не пересекались — можно эффективно за полиномиальное время, как нам известно из классических курсов алгоритмов.

В этом курсе мы изучим множество параметров, описывающих структуру графа. Базовый смысл каждого отдельного параметра — чем больше параметр, тем сложнее структура графа. Параметры могут быть совершенно разнообразными, от, например, средней степени графа, до его древесной ширины (treewidth). Мы исследуем, как эти параметры взаимосвязаны между собой, как их можно эффективно вычислить, а самое главное — как они помогают разработать эффективные алгоритмы для задач, которые вычислительно сложны в общем случае.

Студенты научатся использовать структурные параметры графа как инструмент — превращать наблюдения о структуре в конкретные алгоритмические техники (динамическое программирование по древесной декомпозиции, ILP, ветвление, кернелизация и другие). Отдельным увлекательным элементом курса станет построение общей карты изученных параметров — иерархического графа, отражающего, какие параметры ограничивают друг друга, а какие из них несравнимы, и как устроен весь ландшафт "структурной сложности" целиком.

Пререквизиты курса:

Без них будет трудновато:

• базовые понятия теории графов
• стандартные алгоритмы

Могут пригодиться:

• основы вычислительной сложности
• параметризованные алгоритмы