Построить минимальное связующее дерево, покрывающее определенное подмножество вершин

У меня есть неориентированный граф с положительным краем (V, E), для которого требуется минимальное связующее дерево, покрывающее подмножество k вершин V (проблема дерева Штейнера).

Я не ограничиваю размер связующего дерева до k вершин; скорее я точно знаю, какие k вершин должны быть включены в MST.

Начиная со всего MST, я мог бы обрезать ребра/узлы, пока не получу наименьший MST, содержащий все k.

Я могу использовать алгоритм Prim для получения всего MST и начать удаление ребер/узлов, в то время как MST подмножества k не уничтожается; в качестве альтернативы я могу использовать Floyd-Warshall для получения кратчайших путей всех пар и как-то объединить пути. Есть ли лучшие способы приблизиться к этому?

Ответ 1

Проблема, о которой вы говорили, является известной проблемой NP-hard, называемой дерево Steiner в графиках. В полиномиальное время нет известных решений, и многие считают, что таких решений не существует.

Ответ 2

Здесь много путаницы. На основании того, что говорит OP:

Я не ограничиваю размер связующего дерева до k вершин; скорее я точно знаю, какие k вершин должны быть включены в MST.

Это проблема дерева Штейнера на графиках. Это не проблема k-MST. Проблема дерева Штейнера определяется как таковая:

Учитывая взвешенный граф G = (V, E), подмножество S ⊆ V вершин, и корень r ∈ V, мы хотим найти минимальное дерево весов, которое связывает все вершины в S с р. 1

Как уже упоминалось, эта проблема NP-hard. Поэтому вы можете использовать алгоритм аппроксимации.

Ранние/простые алгоритмы приближения

Два известных метода: метод Такахаши и метод Крускала (оба из которых были расширены/улучшены Rayward-Smith):

Takahashi H, Matsuyama A: приближенное решение задачи Штейнера в графах. Математика Jap 1980, 24: 573-577.
Kruskal JB: о кратчайшем охватывающем субтриге графа и проблеме коммивояжера. В трудах Американского математического общества, том 7.; 1956:. 48-50
Rayward-Smith VJ, Clare A: Об обнаружении вершин Штейнера. Сети 1986, 16: 283-294.

Аппроксимация кратчайшего пути Такахаши (с модификацией Rayward-Smith)

Алгоритм аппроксимации Крускала (с модификацией Rayward-Smith)

Современные/более продвинутые алгоритмы приближения

В биологии более поздние подходы рассматривали проблему с использованием метода полости, что привело к методу "модифицированного распространения верований", который показал хорошую точность в больших наборах данных:

Bayati, M., Borgs, C., Braunstein, A., Chayes, J., Ramezanpour, A., Zecchina, R.: Статистическая механика деревьев steiner. Phys. Rev. Lett. 101 (3), 037208 (2008) 15.
Для приложения: методы дерева Штейнера для оптимальной идентификации подсетей: эмпирическое исследование. BMC Биоинформатика. BMC Bioinformatics 2013 30; 14: 144. Epub 2013 Apr 30.

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

G. Бхалотия, А. Халгери, К. Нахе, С. Чакрабарти и С. Сударшан. Поиск и поиск ключевых слов в базах данных с использованием BANKS. В ICDE, стр. 431-440.
G. Каснеци, М. Раманат, М. Социо, Ф. М. Суханек и Г. Вайкум. STAR: приближение Штайнера-дерева в графах отношений. В ICDE09, страницы 868-879, 2009

Ответ 3

Выполнить алгоритм Prim на ограниченном графе (k, E '), где E' = {(x, y) ∈ V: x ∈ k и y ∈ k}). Построение этого графа принимает O (| E |).