Техника Бренды Бейкер

Техника Бренды Бейкер — это метод построения приближенных схем полиномиального времени (ПСПВ, PTAS) для задач на планарных графах. Метод назван именем американской учёной в области информатики Бренды Бейкер, сообщившей о методе на конференции 1983 года и опубликовавшей статью в журнале Journal of the ACM в 1994.

Идея техники Бренды Бейкер заключается в разбиении графа на уровни, так что задача может быть решена оптимально на каждом уровне, затем решения на каждом уровне комбинируются удовлетворительным способом, что приводит к реалистичному решению. Эта техника дала ПСПВ для следующих задач: задача поиска изоморфного подграфа, задача о максимальном независимом множестве, задача о вершинном покрытии, минимальное доминирующее множество, минимальное доминирующее множество рёбер многие другие.

Теория двухмерности Эрика Демайна, Фёдора Фомина, Мухаммеда Хаджигайи и Димитроса Тиликоса и её ответление упрощённые декомпозиции обобщает и существенно расширяет область применения техники Бренды Бейкер на обширное множество задач на планарных графах и, более обще, на графах, не содержащих определённого минора, таких как графы с ограниченным родом, а также другие классы графов, не замкнутые по взятию минора, такие как 1-планарные графы.

Пример техники

Пример, на котором продемонстрируем технику Бренды Бейкер — это задача нахождения максимума взвешенного независимого множества.

Алгоритм

НЕЗАВИСИМОЕ МНОЖЕСТВО($G$,$w$,$\epsilon$)

Выбираем произвольную вершину $r$
$k=1/\epsilon$
Находим уровни поиска в ширину для графа $G$ с корнем $r$ ${\pmod {k}}$: $\{V_{0},V_{1},\ldots ,V_{k-1}\}$
Для всех $\ell =0,\ldots ,k-1$
Находим компоненты $G_{1}^{\ell },G_{2}^{\ell },\ldots ,$ графа $G$ после удаления уровня $V_{\ell }$
Для всех $i=1,2,\ldots$
Вычисляем  $S_{i}^{\ell }$, независимое множество с максимальным весом для графа  $G_{i}^{\ell }$
$S^{\ell }=\cup _{i}S_{i}^{\ell }$
Пусть $S^{\ell ^{*}}$ является решением задачи с максимальным весом среди $\{S^{0},S^{1},\ldots ,S^{k-1}\}$
Возвращаем $S^{\ell ^{*}}$

Заметим, что приведённый алгоритм правдоподобен, поскольку каждое множество $S^{\ell }$ является объединением непересекающихся независимых множеств.

Динамическое программирование

Динамическое программирование используется для вычисления независимого множества максимального веса для каждого $G_{i}^{\ell }$. Эта задача динамического программирования работает, поскольку каждый граф $G_{i}^{\ell }$ является $k$-внешнепланарным. Многие NP-полные задачи можно решить с помощью динамического программирования на $k$-внешнепланарных графах.