Рандомизированный алгоритм нахождения минимального остовного дерева
Постановка задачи
На входе имеется связный неориентированный граф G = (V, E) с весом w(e) каждого ребра [math]\displaystyle{ e \in E \; }[/math]. Задача заключается в нахождении остовного дерева с минимальным весом, где для любого подмножества ребер [math]\displaystyle{ E' \subseteq E \; }[/math] вес E' определяется как [math]\displaystyle{ w(E') = \sum_{e \in E'} w(e) \; }[/math].
Если граф G не является связным, задача заключается в нахождении минимального остовного леса, который определяется как совокупность минимальных остовных деревьев для каждой связной компоненты G. Обе задачи будут обозначаться как MST (minimum spanning tree).
Рандомизированный алгоритм MST авторства Карджера, Клейна и Тарьяна [9] будет далее обозначаться как алгоритм KKT. Также будем считать, что входной граф G = (V, E) имеет n вершин и m ребер и что все веса ребер различны.
Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время выполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [1], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [5]) и Крускала [5].
Самый быстрый известный алгоритм MST до создания KKT выполнялся за время [math]\displaystyle{ O(m \; log \; \beta (m, n)) }[/math] [7], где [math]\displaystyle{ \beta (m, n) = min \{ i \; | \; log^{(i)} n \le m/n \} }[/math] [7]; здесь [math]\displaystyle{ log^{(i)} n \; }[/math] определяется как [math]\displaystyle{ log \; n }[/math], если i = 1, и [math]\displaystyle{ log \; log^{(i - 1)} n \; }[/math], если i > 1. Хотя это время выполнения близко к линейному, оно не является линейным в случае очень разреженных графов.
Задача эффективного нахождения минимального остовного дерева представляет собой важнейшую фундаментальную проблему в сферах алгоритмов на графах и комбинаторной оптимизации.
Контекст и история
Вспомним некоторые важные исторические данные.
• Основной компонент алгоритма Борувки [1] – «шаг Борувки», который выбирает ребро с минимальным весом, инцидентное каждой вершине, добавляет его к минимальному остовному дереву и затем выполняет сжатие данных ребер. Этот шаг выполняется за линейное время и поддается эффективному распараллеливанию. Он стал основой для самых эффективных параллельных алгоритмов поиска минимального остовного дерева; этот подход также используется алгоритмом KKT.
• Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [13]; позднее был разработан детерминированный алгоритм с линейным временем выполнения [6] (см. также более простой алгоритм в [12]).
Основные результаты
Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время выполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью [math]\displaystyle{ 1 - exp( - \Omega (m)) \; }[/math], а время выполнения в наихудшем случае составит O(n + m log n).
Простая и элегантная лемма выборки для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов:
1. Хорошо известное свойство циклов для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G не может входить в состав минимального остовного дерева.
2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро [math]\displaystyle{ e \in E \; }[/math] называется F-легким, если имеет место один из двух случаев: (1) [math]\displaystyle{ F \cup \{ e \} \; }[/math] продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G независимо от того, какой лес F используется. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева с линейным временем выполнения [6, 12].
Лемма 1 (лемма выборки для задачи MST). Пусть [math]\displaystyle{ H = (v, E_H) \; }[/math] создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G не превышает n/p.
Алгоритм KKT определяет ребра минимального остовного дерева G, используя только шаги Борувки. После каждых двух шагов Борувки он выполняет удаление F-тяжелых ребер, используя минимальный остовный лес F подграфа, полученный посредством выборки ребер с вероятностью p = 1/2. Как упоминалось ранее, эти F-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом.
Корректность алгоритма KKT очевидна, так как каждое удаляемое им F-тяжелое ребро не может входить в состав минимального остовного дерева (МОД) графа G, поскольку F – лес G, а каждое ребро, добавляемое им к минимальному остовному дереву, входит в состав МОД, поскольку добавляется при помощи шага Борувки.
Анализ ожидаемого времени выполнения и экспоненциально высокая граница вероятности для времени выполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1).
В работе [9] доказываются следующие положения.
Теорема 2. Алгоритм KKT представляет собой рандомизированный алгоритм, вычисляющий минимальное остовное дерево неориентированного графа с n вершин и m взвешенных ребер за время O(n + m) с вероятностью не менее [math]\displaystyle{ 1 - exp( - \Omega (m)) \; }[/math]. Ожидаемое время выполнения составляет O(n + m), а в наихудшем случае – O(m + n log n).
В качестве модели вычислений в [9] использовалась RAM-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели машины с указателями. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2].
Лемма 1 была доказана в [9] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [3].
Дополнительные соображения
• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [14]. Первый [4] выполняется за время [math]\displaystyle{ O(n + m \alpha(m, n)) \; }[/math], где [math]\displaystyle{ \alpha \; }[/math] – обратная функция Аккермана, которая растет даже медленнее, чем функция [math]\displaystyle{ \beta \; }[/math], ранее упоминавшаяся в качестве наилучшего результата, известного до публикации алгоритма KKT [4]. Второй алгоритм [14] доказуемо выполняется за время, не более чем на константный множитель отличающееся от сложности дерева решений задачи минимального остовного дерева и, следовательно, являющееся оптимальным; его временные границы составляют [math]\displaystyle{ O(n + m \alpha (m, n)) \; }[/math] и [math]\displaystyle{ \Omega (n + m) \; }[/math], точные границы еще не определены.
• Хотя ожидаемое время выполнения алгоритма KKT является линейным (с экспоненциально высокой вероятностью), это не лучший показатель среди рандомизированных MST-алгоритмов. Рандомизированный MST-алгоритм, выполняющийся за ожидаемое линейное время и использующий только [math]\displaystyle{ O(log^* \; n) }[/math] случайных бит, приведен в работах [16, 17]. Для сравнения, алгоритм KKT использует линейное количество случайных бит.
Применение
Задача нахождения минимального остовного дерева широко применяется на практике; подробнее об этом – в соответствующей статье.
Открытые вопросы
Остаются нерешенными следующие задачи:
1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он выполняется за ожидаемое линейное время и использует только [math]\displaystyle{ O(log^* \; n) }[/math] случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT.
2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [10] для MST? Линейный по числу операций параллельный MST-алгоритм с ожидаемым логарифмическим временем выполнения для EREW PRAM приведен в [15]. Этот алгоритм является оптимальным и с точки зрения операций, и с точки зрения временных затрат. Однако он использует линейное количество случайных бит. В [16, 17] приведен оптимальный с точки зрения операций параллельный алгоритм, выполняющийся за ожидаемое полилогарифмическое время и использующий только полилогарифмическое число случайных бит. В силу этого интересны следующие, пока открытые, вопросы, касающиеся параллельных алгоритмов для задачи MST:
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST?
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного выполнения)?
Экспериментальные результаты
Катриэль, Сандерс и Трафф [11] выполнили экспериментальную оценку алгоритма KKT и показали, что он демонстрирует высокую эффективность на относительно плотных графах.
См. также
Литература
1. Boruvka, O.: O jistem problemu minimalnim. Prace Moravske Pfirodovedecke Spolecnosti 3,37-58 (1926) (In Czech)
2. Buchsbaum, A., Kaplan, H., Rogers, A., Westbrook, J.R.: Linear-time pointer-machine algorithms for least common ancestors, MST verification and dominators. In: Proc. ACM Symp. on Theory of Computing (STOC), 1998, pp. 279-288
3. Chan, T.M.: Backward analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees. Inf. Process. Lett. 67, 303-304(1998)
4. Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028-1047 (2000)
5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)
6. Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21 (6), 1184-1192(1992)
7. Gabow, H.N., Galil, Z., Spencer, T.H., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Comb. 6,109-122(1986)
8. Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7(1), 43-57 (1985)
9. Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. J. ACM 42(2), 321-329(1995)
10. Karp, R.M., Ramachandran, V.: Parallel algorithms for shared-memory machines. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, pp. 869-941. Elsevier Science Publishers B.V., Amsterdam (1990)
11. Katriel, I., Sanders, P., Traff, J.L.: A practical minimum spanning tree algorithm using the cycle property. In: Proc. 11th Annual European Symposium on Algorithms. LNCS, vol. 2832, pp. 679-690. Springer, Berlin (2003)
12. King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica 18(2), 263-270 (1997)
13. Komlos, J.: Linear verification for spanning trees. Combinatorica 5(1), 57-65(1985)
14. Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16-34 (2002)
15. Pettie, S., Ramachandran, V.: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. SI AM J. Comput. 31 (6), 1879-1895 (2002)
16. Pettie, S., Ramachandran, V.: Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002, pp. 713-722
17. Pettie, S., Ramachandran, V.: New randomized minimum spanning tree algorithms using exponentially fewer random bits. ACM Trans. Algorithms. 4(1), article 5 (2008)