Минимальное остовное дерево в графе с несколькими корневыми вершинами

Question

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

При заданном наборе корневых вершин [1,4,6] и графе G, как на следующем рисунке:

... алгоритм должен возвращать что-то вроде зеленого подграфа на том же рисунке.

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

Примечания:

1. Я знаю, что нет MST для ориентированного графа, но есть алгоритм Чу-Лю / Эдмондса .
2. Я предполагаю, что это результат такого алгоритма (если это действительно возможно) вернет оптимальное ветвление, которое включает в себя несколько вершин графа вместе со всеми корневыми вершинами.

Answer 1

Минимальные остовные деревья должны охватывать все вершины. Я думаю, что вы на самом деле имеете дело с проблемой Steiner Tree , учитывая, что вам нужно только подключить их подмножество. К сожалению, традиционная проблема дерева Штейнера с ненаправленными ребрами уже завершена, так что вам предстоит трудный путь.