Алгоритмы динамического программирования на графах с ограниченной древесной шириной

Фундаментальное понятие древесной декомпозиции (Tree Decomposition), введенное Робертсоном и Сеймуром в рамках их монументального труда по минорам графов, представляет собой способ математического отображения произвольного графа на древовидную структуру. Каждому узлу дерева ставится в соответствие подмножество вершин исходного графа. Декомпозиция должна удовлетворять трем строгим аксиомам: каждая вершина графа должна присутствовать хотя бы в одной сумке, концы любого ребра графа должны встречаться вместе хотя бы в одной сумке, и узлы дерева, содержащие определенную вершину графа, должны образовывать связное поддерево. Размер наибольшей сумки минус единица называется шириной данной декомпозиции.

Древесная ширина графа определяется как минимальная возможная ширина среди всех возможных древесных декомпозиций этого графа. Графы с древесной шириной 1 — это обычные деревья; графы с шириной 2 — это параллельно-последовательные графы. Ключевая алгоритмическая ценность древесной ширины заключается в том, что она является мерой того, насколько данный граф похож на дерево. Если древесная ширина графа ограничена небольшой константой $k$, то задача декомпозируется на слабо связанные фрагменты, что открывает путь для применения мощнейшего аппарата динамического программирования.

Алгоритм динамического программирования работает путем восходящего прохода по дереву декомпозиции, начиная от листьев и заканчивая корнем. В каждом узле-сумке вычисляются частичные решения задачи для подграфа, образованного вершинами этой сумки и всех ее потомков в дереве. Поскольку размер любой сумки не превышает $k+1$, количество возможных частичных конфигураций, которые необходимо перебрать в одном узле, ограничено функцией, зависящей только от $k$. Комбинируя частичные решения в узлах слияния с использованием рекуррентных соотношений, алгоритм вычисляет глобальный оптимум за время, линейно зависящее от числа вершин графа. Таким образом, экспоненциальная сложность полностью локализуется в параметре $k$.

Обобщением этих алгоритмических достижений стала знаменитая Метатеорема Курселя (Courcelle Theorem). Она строго математически доказывает, что абсолютно любая задача на графах, которую можно сформулировать на языке Монадической логики второго порядка, гарантированно решается за линейное время на графах с ограниченной древесной шириной. Это касается поиска гамильтоновых циклов, клик максимального размера и задач о покрытиях. В области машинного обучения алгоритмы точного логического вывода на байесовских сетях являются прямым воплощением динамического программирования на древесной декомпозиции, доказывая универсальность данного математического аппарата.

Список литературы:
1. Bodlaender H.L. A Tourist Guide through Treewidth. — Acta Cybernetica, 1993.
2. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014.
3. Downey R.G., Fellows M.R. Parameterized Complexity. — Springer, 1999.