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

НЕЗАВИСИМОЕ МНОЖЕСТВО(${\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}$-внешнепланарных графах.