Выбор k подпостов

Question

Я столкнулся со следующей алгоритмической проблемой, экспериментируя с алгоритмами классификации.Элементы классифицируются в многоуровневую структуру, что, как я понимаю, представляет собой набор с одним корнем.Я должен решить следующую проблему, которая очень похожа на проблему покрытия комплекта .

Я загрузил свое описание проблемы с латексным шрифтом здесь .

Разработать алгоритм аппроксимации, который удовлетворяет требованиям 1 и 2, довольно просто, просто начните с вершин G и «поднимайтесь» или начинайте с корня и «уходите».Допустим, вы начинаете с корня, итеративно расширяете вершины, а затем удаляете ненужные вершины, пока у вас не будет хотя бы k подрешеток.Граница аппроксимации зависит от количества дочерних элементов вершины, что нормально для моего приложения.

Кто-нибудь знает, имеет ли эта проблема собственное имя, или, возможно, древовидную версию проблемы?Мне было бы интересно узнать, является ли эта проблема NP-трудной, может быть, у кого-то есть идеи для хорошей NP-трудной задачи, которую можно уменьшить, или есть полиномиальный алгоритм для решения проблемы.Если у вас обоих есть ваша цена в миллион долларов .;)

Answer 1

Версия DAG жесткая (барабанная дробь) по сравнению с установленной крышкой. Установите k = 2 и сделайте очевидное: условие (2) не позволяет нам получить корень. (Обратите внимание, что (3) на самом деле не означает (2) из-за нижней границы k.)

Древовидная версия является частным случаем версии с параллельными рядами, которая может быть решена точно за полиномиальное время. Вот рекурсивная формула, которая дает полином p (x), где коэффициент x ⁿ является числом покрытий мощности n.

Одна покрываемая вершина: p (x) = x.

Другая вершина: p (x) = 1 + x.

Параллельная композиция, где q и r - многочлены для двух поцетов: q (x) r (x).

Состав рядов, где q - это многочлен для верхнего множества и r для нижнего: если верхнее множество не содержит покрываемых вершин, то p (x) = (q (x) - 1) + r Икс); в противном случае p (x) = q (x).