Динамическое программирование и древовидная декомпозиция

Мы начали с утверждения о том, что задача о независимом множестве с максимальным весом может быть эффективно решена для любого графа с ограниченной древовидной шириной. Пришло время выполнить обещание, а именно: мы разработаем алгоритм, который точно следует алгоритму с линейным временем для деревьев.

Итак, в очень конкретном смысле сложность задачи была переведена из размера графа в древовидную ширину, которая может быть намного меньше.

Как упоминалось ранее, большие сети в реальном мире часто имеют очень малую древовидную ширину; и часто эта особенность проявляется не случайно, а вследствие структурированного или модульного подхода к их планированию.

Итак, если вы имеете дело с сетью из 1000 узлов с древовидной декомпозицией ширины 4, рассматриваемый метод позволяет преобразовать безнадежно неразрешимую задачу в потенциально выполнимую.

Конечно, ситуация отчасти напоминает алгоритм вершинного покрытия из раздела 10.1. Тогда экспоненциальная сложность была переведена в параметр k, размер искомого вершинного покрытия. На этот раз очевидного параметра, кроме n, не видно, поэтому нам пришлось изобрести неочевидный: древовидную ширину.

Чтобы разработать алгоритм, вспомним, что было сделано в случае дерева T. После определения корня T мы построили независимое множество, двигаясь вверх от листьев.

В каждом внутреннем узле u мы перебираем возможные решения относительно узла u (включать или не включать), так как после фиксирования этого решения задачи разных поддеревьев под u становятся независимыми.

Обобщение для графа G с древовидной декомпозицией (T, {Vt}) ширины w выглядит очень похоже. Мы закрепляем корень T и строим независимое множество, рассматривая фрагменты Vt от листьев вверх.

Во внутреннем узле t из T мы сталкиваемся со следующим основным вопросом: оптимальное независимое множество пересекает фрагмент Vt в некотором подмножестве U, но мы не знаем, какое это множество U.

Соответственно мы перебираем все возможности для этого подмножества U, то есть все возможности относительно того, какие узлы из Vt включать, а какие не включать.

Поскольку Vt может иметь размер до w + 1, появляется до 2w+1 рассматриваемых возможностей. Но теперь можно использовать два ключевых факта: во-первых, величина 2w+1 намного разумнее 2n, когда w намного меньше n; и во-вторых, после фиксирования конкретной возможности 2w+1 (когда мы решим, какие узлы в фрагменте Vt будут включены), свойства разбиения (10.13) и (10.14) гарантируют, что задачи разных поддеревьев T под t могут решаться независимо.

Таким образом, хотя мы довольствуемся поиском «грубой силы» на уровне одного фрагмента, в целом алгоритм достаточно эффективно работает на глобальном уровне при малом количестве отдельных фрагментов.