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

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

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

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

Пример техникиПравить

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

АлгоритмПравить

НЕЗАВИСИМОЕ МНОЖЕСТВО($G$$G$ ,$w$$w$ ,$\mathrm{ϵ<!--\; ϵ\; -->}$$\epsilon$ )

Выбираем произвольную вершину $r$$r$ 
$k=1/\mathrm{ϵ<!--\; ϵ\; -->}$$k=1/\epsilon$ 
Находим уровни поиска в ширину для графа $G$$G$  с корнем $r$$r$  $(\mathrm{mod}k)$${\pmod {k}}$ : $\{V_0,V_1,\dots <!--\; \dots \; -->,V_{k-<!--\; -\; -->1}\}$$\{V_{0},V_{1},\ldots ,V_{k-1}\}$ 
Для всех $\mathrm{\ell <!--\; \ell \; -->}=0,\dots <!--\; \dots \; -->,k-<!--\; -\; -->1$$\ell =0,\ldots ,k-1$ 
Находим компоненты $G_1^{\mathrm{\ell <!--\; \ell \; -->}},G_2^{\mathrm{\ell <!--\; \ell \; -->}},\dots <!--\; \dots \; -->,$$G_{1}^{\ell },G_{2}^{\ell },\ldots ,$  графа $G$$G$  после удаления уровня $V_{\mathrm{\ell <!--\; \ell \; -->}}$$V_{\ell }$ 
Для всех $i=1,2,\dots <!--\; \dots \; -->$$i=1,2,\ldots$ 
Вычисляем  $S_i^{\mathrm{\ell <!--\; \ell \; -->}}$$S_{i}^{\ell }$ , независимое множество с максимальным весом для графа  $G_i^{\mathrm{\ell <!--\; \ell \; -->}}$$G_{i}^{\ell }$ 
$S^{\mathrm{\ell <!--\; \ell \; -->}}={\cup <!--\; \cup \; -->}_i{S}_i^{\mathrm{\ell <!--\; \ell \; -->}}$$S^{\ell }=\cup _{i}S_{i}^{\ell }$ 
Пусть $S^{{\mathrm{\ell <!--\; \ell \; -->}}^{\ast <!--\; \ast \; -->}}$$S^{\ell ^{*}}$  является решением задачи с максимальным весом среди $\{S^0,S^1,\dots <!--\; \dots \; -->,S^{k-<!--\; -\; -->1}\}$$\{S^{0},S^{1},\ldots ,S^{k-1}\}$ 
Возвращаем $S^{{\mathrm{\ell <!--\; \ell \; -->}}^{\ast <!--\; \ast \; -->}}$$S^{\ell ^{*}}$ 

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

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

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