Randomized minimum spanning tree algorithms using exponentially fewer random bits

For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis problem, the parallel connected components and parallel minimum spanning tree problems, and the local sorting and set maxima problems. (For the first two problems there are provably optimal deterministic algorithms with unknown, and possibly superlinear, running times.) One downside of the randomized methods for solving these problems is that they use a number of random bits linear in the size of input. In this article we develop some general methods for reducing exponentially the consumption of random bits in comparison-based algorithms. In some cases we are able to reduce the number of random bits from linear to nearly constant, without affecting the expected running time. Most of our results are obtained by adjusting or reorganizing existing randomized algorithms to work well with a pairwise or O(1)-wise independent sampler. The prominent exception, and the main focus of this article, is a linear-time randomized minimum spanning tree algorithm that is not derived from the well-known Karger-Klein-Tarjan algorithm. In many ways it resembles more closely the deterministic minimum spanning tree algorithms based on soft heaps. Further, using our algorithm as a guide, we present a unified view of the existing “nongreedy” minimum spanning tree algorithms. Concepts from the Karger-Klein-Tarjan algorithm, such as F-lightness, MST verification, and sampled graphs, are related to the concepts of edge corruption, subgraph contractibility, and soft heaps, which are the basis of the deterministic MST algorithms of Chazelle and Pettie-Ramachandran.

对于许多基本问题，存在渐近最优且优于已知最佳确定性算法的随机算法。其中包括最小生成树（MST）问题、MST敏感性分析问题、并行连通分量和并行最小生成树问题，以及局部排序和集合最大值问题。（对于前两个问题，存在可证明最优的确定性算法，其运行时间未知，可能是超线性的。）解决这些问题的随机方法的一个缺点是，它们使用的随机比特数与输入规模呈线性关系。在本文中，我们开发了一些通用方法，用于在基于比较的算法中以指数方式减少随机比特的消耗。在某些情况下，我们能够将随机比特数从线性减少到接近常数，而不影响预期运行时间。 我们的大多数结果是通过调整或重新组织现有的随机算法，使其与成对或O(1) - 独立采样器良好配合而获得的。一个突出的例外，也是本文的主要关注点，是一个线性时间随机最小生成树算法，它不是从著名的卡格尔 - 克莱因 - 塔尔扬算法推导出来的。在很多方面，它更类似于基于软堆的确定性最小生成树算法。此外，以我们的算法为指导，我们对现有的“非贪心”最小生成树算法提出了一个统一的观点。卡格尔 - 克莱因 - 塔尔扬算法中的概念，如F - 轻性、MST验证和采样图，与边损坏、子图可收缩性和软堆等概念相关，这些概念是查泽尔以及佩蒂 - 拉马钱德兰的确定性MST算法的基础。