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

Те́хніка Бре́нди Бе́йкер — метод побудови схем наближення до поліноміального часу (СНПЧ, PTAS) для задач на планарних графах. Метод названо ім'ям американської вченої в галузі інформатики ^[en], яка повідомила про метод на конференції 1983 року і опублікувала статтю в журналі у 1994.

Ідея техніки Бренди Бейкер полягає в розбитті графа на рівні, так що задачу можна розв'язати оптимально на кожному рівні, потім розв'язки на кожному рівні комбінуються задовільним способом, що дає реалістичний розв'язок. Ця техніка дала СНПЧ для таких задач: задача пошуку ізоморфного підграфа, задача про максимальну незалежну множину, задача про вершинне покриття, мінімальна домінівна множина, мінімальна домінівна множина ребер та багато інших.

^[en] Еріка Демайна, Федора Фомина, Мухаммеда Хаджигайї та Димитроса Тілікоса і її відгалуження спрощені декомпозиції узагальнює й істотно розширює сферу застосування техніки Бренди Бейкер на багато задач на планарных графах і, загальніше, на графах, які не містять певного мінора, таких як графи з обмеженим родом, а також інші класи графів, не замкнуті після взяття мінора, такі як 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 // . — 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.