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

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

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

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

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

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

Алгоритм

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

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

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

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

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

Примечания

1. Demaine, Hajiaghayi, Kawarabayashi, 2005.
2. Demaine, Hajiaghayi, Kawarabayashi, 2011.

Литература

• B. Baker. Approximation algorithms for NP-complete problems on planar graphs // Journal of the ACM. — 1994. — Т. 41, вып. 1. — С. 153–180. — doi:10.1145/174644.174650.
• B. Baker. Approximation algorithms for NP-complete problems on planar graphs // FOCS. — 1983. — Т. 24.
• H. Bodlaender. Dynamic programming on graphs with bounded treewidth // ICALP. — 1988. — doi:10.1007/3-540-19488-6_110.
• E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring // FOCS. — 2005. — Т. 46. — doi:10.1109/SFCS.2005.14.
• E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Contraction decomposition in H-minor-free graphs and algorithmic applications // STOC. — 2011. — Т. 43. — doi:10.1145/1993636.1993696.
• E. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, D. Thilikos. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. // J. Comput. Syst. Sci.. — 2004. — Т. 69. — doi:10.1016/j.jcss.2003.12.001.
• D. Eppstein. Diameter and treewidth in minor-closed graph families. // Algorithmica. — 2000. — Т. 27. — doi:10.1007/s004530010020. — arXiv:math/9907126v1.
• D. Eppstein. Subgraph isomorphism in planar graphs and related problems. // SODA. — 1995. — Т. 6.
• Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // Algorithmica. — 2007. — Т. 49, вып. 1. — С. 1–11. — doi:10.1007/s00453-007-0010-x.