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

Те́хніка Бре́нди Бе́йкер — метод побудови схем наближення до поліноміального часу (СНПЧ, 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$-зовніпланарних графах.

Література

• 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. — arXiv:math/9907126v1. — DOI:10.1007/s004530010020.
• 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.