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

Question

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

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

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

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

Answer 1

Здесь много путаницы.Исходя из того, что ОП говорит:

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

Это проблема дерева Штейнера на графах. Это непроблема k-MST. Задача дерева Штейнера определяется следующим образом:

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

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

Ранние / простые алгоритмы аппроксимации

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

• Такахаши Х, Мацуяма А: Приближенное решение проблемы Штейнера на графах.МатематикаJap 1980, 24: 573–577.
• Крускал Дж. Б. О кратчайшем расширяющемся поддереве графа и проблеме коммивояжера.В трудах Американского математического общества, том 7.;1956: 48–50.
• Рейвард-Смит В.Дж., Клэр А. Об обнаружении вершин Штейнера.Networks 1986, 16: 283–294.

---

Приближение кратчайшего пути Такахаси (с модификацией Рэйворда-Смита)

---

алгоритм приближения Крускала (с модификацией Рэйворда-Смита)

---

Современные / более продвинутые алгоритмы аппроксимации

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

• Баяти, М., Боргс, С., Браунштейн, А., Чайес, Дж., Рамезанпур, А., Зекчина, Р .: Статистическая механикаштейнеров.Phys.Преподобный Летт.101 (3), 037208 (2008) 15.
• Для приложения: методы дерева Штейнера для оптимальной идентификации подсети: эмпирическое исследование.БМК Биоинформатика.BMC Bioinformatics 2013 30; 14: 144.Epub 2013 Apr 30.

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

• Г.Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti и S. Sudarshan.Поиск и просмотр ключевых слов в базах данных с использованием БАНКОВ.В ICDE, стр. 431–440.
• G.Kasneci, M. Ramanath, M. Sozio, FM Suchanek, G. Weikum.STAR: аппроксимация по Штейнеру в графах отношений.В ICDE'09, стр. 868–879, 2009

Answer 2

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

Answer 3

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