Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями

Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время исполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [1], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [5]) и Крускала [5].

Самый быстрый известный алгоритм MST до создания KKT исполнялся за время <math>O(m \; log \; \beta (m, n))</math> [7], где <math>\beta (m, n) = min \{ i \; | \; log^{(i)} n \le m/n \}</math> [7]; здесь <math>log^{(i)} n \;</math> определяется как <math>log \; n</math>, если i = 1, и <math>log \; log^{(i - 1)} n \;</math>, если i > 1. Хотя это время исполнения близко к линейному, оно не является линейным в случае очень разреженных графов.

• Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [13]; позднее был разработан детерминированный алгоритм с линейным временем исполнения [6] (см. также более простой алгоритм в [12]).

Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время исполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью <math>1 - exp( - \Omega (m)) \;</math>, а время исполнения в наихудшем случае составит O(n + m log n).

2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро <math>e \in E \;</math> называется F-легким, если имеет место один из двух случаев: (1) <math>F \cup \{ e \} \;</math> продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G н''езависимо от того, какой лес F используется''. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева с линейным временем исполнения [6, 12].

Корректность алгоритма KKT очевидна, поскольку каждое удаляемое им F-тяжелое ребро не может входить в состав минимального остовного дерева (МОД) графа G, поскольку F – лес G, а каждое ребро, добавляемое им к минимальному остовному дереву, входит в состав МОД, поскольку добавляется при помощи шага Борувки.

'''Теорема 2. Алгоритм KKT представляет собой рандомизированный алгоритм, вычисляющий минимальное остовное дерево неориентированного графа с n вершин и m взвешенных ребер за время O(n + m) с вероятностью не менее <math>1 - exp( - \Omega (m)) \;</math>. Ожидаемое время исполнения составляет O(n + m), а в наихудшем случае – O(m + n log n).'''

В качестве модели вычислений в [9] использовалась RAM-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели машины с указателями. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2].

• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [14]. Первый [4] исполняется за время <math>O(n + m \alpha(m, n)) \;</math>, где <math>\alpha \;</math> – обратная функция Аккермана, которая растет даже медленнее, чем функция <math>\beta \;</math>, ранее упоминавшаяся в качестве наилучшего результата, известного до публикации алгоритма KKT [4]. Второй алгоритм [14] доказуемо исполняется за время, не более чем на константный множитель отличающееся от сложности дерева решений задачи минимального остовного дерева и, следовательно, являющееся оптимальным; его временные границы составляют <math>O(n + m \alpha (m, n)) \;</math> и <math>\Omega (n + m) \;</math>, точные границы еще не определены.

• Хотя ожидаемое время исполнения алгоритма KKT является линейным (с экспоненциально высокой вероятностью), это не лучший показатель среди рандомизированных MST-алгоритмов. Рандомизированный MST-алгоритм, исполняющийся за ожидаемое линейное время и использующий только <math>O(log^* \; n)</math> случайных бит, приведен в работах [16, 17]. Для сравнения, алгоритм KKT использует линейное количество случайных бит.

1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он исполняется за ожидаемое линейное время и использует только <math>O(log^* \; n)</math> случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT.

2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [10] для MST? Линейный по числу операций параллельный MST-алгоритм с ожидаемым логарифмическим временем исполнения для EREW PRAM приведен в [15]. Этот алгоритм является оптимальным и с точки зрения операций, и с точки зрения временных затрат. Однако он использует линейное количество случайных бит. В [16, 17] приведен оптимальный с точки зрения операций параллельный алгоритм, исполняющийся за ожидаемое полилогарифмическое время и использующий только полилогарифмическое число случайных бит. В силу этого интересны следующие, пока открытые, вопросы, касающиеся параллельных алгоритмов для задачи MST:

• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного исполнения)?