Решение NP-сложных задач для деревьев

В разделе 10.1 мы разработали алгоритм для задачи о вершинном покрытии, который хорошо работает при не слишком большом размере покрытия. Было показано, что найти относительно малое вершинное покрытие намного проще, чем в полностью обобщенной задаче вершинного покрытия.

Дело даже не только в структурной простоте таких деревьев, но и в том, что многие NP-сложные задачи графов эффективно решаются в том случае, если нижележащий граф является деревом.

На качественном уровне это объясняется следующим образом: если рассмотреть поддерево входных данных с корнем в некотором узле v, решение задачи, ограничиваемое этим поддеревом, «взаимодействует» с остатком дерева через v.

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

Чтобы формализовать этот общий подход и преобразовать его в эффективный алгоритм, потребуются определенные усилия.

Сейчас вы увидите, как это делается для разновидностей задачи о независимом множестве; однако важно помнить, что этот принцип достаточно общий, и с таким же успехом можно было рассмотреть для деревьев многие другие NP-полные задачи графов.

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

Вы увидите, что задача о независимом множестве с максимальным весом решается для деревьев средствами динамического программирования с использованием довольно прямолинейной реализации описанных выше рассуждений.