Задача вершинного покрытия (решение динамического программирования для дерева)

Вершинное покрытие неориентированного графа — это подмножество его вершин, такое что для каждого ребра (u, v) графа либо u, либо v находится в вершинном покрытии. Хотя это и называется Vertex Cover, набор покрывает все ребра данного графа.
Задача нахождения вершинного покрытия графа минимального размера является NP-полной. Но для деревьев ее можно решить за полиномиальное время. В этом посте обсуждается решение для двоичного дерева. Это же решение можно распространить на n-арные деревья.

Например, рассмотрим следующее бинарное дерево. Наименьшее вершинное покрытие равно {20, 50, 30}, а размер вершинного покрытия равен 3.

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

2) Корень не является частью вершинного покрытия: в этом случае оба потомка корня должны быть включены в вершинное покрытие, чтобы покрыть все ребра от корня до дочерних. Мы рекурсивно вычисляем размер вершинных покрытий всех внуков и количество детей к результату (для двух детей корня).

Ниже приведена реализация вышеуказанной идеи.

Выход:

Size of the smallest vertex cover is 3

Временная сложность описанного выше наивно-рекурсивного подхода экспоненциальна. Следует отметить, что приведенная выше функция снова и снова вычисляет одни и те же подзадачи. Например, vCover узла со значением 50 оценивается дважды, так как 50 является потомком 10 и потомком 20.

Поскольку одни и те же подзадачи вызываются снова, эта задача имеет свойство Перекрывающиеся подзадачи. Таким образом, задача вершинного покрытия обладает обоими свойствами (см. это и это) задачи динамического программирования. Как и в случае с другими типичными задачами динамического программирования (DP), повторных вычислений одних и тех же подзадач можно избежать, сохраняя решения подзадач и решая проблемы восходящим образом.

Ниже приведена реализация решения на основе динамического программирования. В следующем решении к узлам дерева добавляется дополнительное поле vc. Начальное значение 'vc' установлено равным 0 для всех узлов. Рекурсивная функция vCover() вычисляет vc для узла только в том случае, если он еще не установлен.

Выход:

Size of the smallest vertex cover is 3

Использованная литература:
http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdf
Упражнение:
Расширьте приведенное выше решение для n-арных деревьев.
Эта статья предоставлена Удит Гупта . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

Подход для любого общего дерева:

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

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

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

узлы в вершинном покрытии, чтобы получить минимальное вершинное покрытие.

3. Мы будем хранить вышеуказанную информацию в массиве dp.

Временная сложность: O(N)

Вспомогательное пространство: O(N)