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

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

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

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

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

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

Алгоритм

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья