Пусть G = (V, E) - неориентированный граф. Подмножество S ⊆ V узлов в G называется «доминирующим множеством», если для всех v ∈ V мы имеем v ∈ S или существует некоторый узел u ∈ S такой, что (u, v) ∈ E. Другими словами, каждый узел в V \ S связан ребром с некоторым узлом в S. Учитывая неотрицательные веса w (v) на узлах V, цель состоит в том, чтобы найти доминирующее множество с минимальным весом в G. (Примечание: эта проблема в общих графах это NP-Hard) Нам нужно разработать алгоритм ПОЛИНОМИАЛЬНОГО времени для этой проблемы, когда G - дерево.

Я читал о проблеме дерева Штейнера в Wiki, которая в некоторой степени связана с этим, но все еще запутана.

Как нам нужно идти об этом?