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

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

Теорія двовимірності^[en] Еріка Демайна, Федора Фомина, Мухаммеда Хаджигайї та Димитроса Тілікоса і її відгалуження спрощені декомпозиції^[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}$-зовніпланарних графах.