Communication-optimal parallel minimum spanning tree algorithms

Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the BSP model are presented. We provide the first non-trivial lower bounds on the communication volume required to solve the MST problem. Let p denote the number of processors, n the number of nodes of the input graph, and m the number of edges of the input graph. We show that in the worst case a total of Ω(k · min(m, pn)) bits need to be transmitted in order to solve the MST problem, where k is the number of bits required to represent a single edge weight. This implies that if a message can contain at most O(k) bits, any BSP algorithm for finding an MST requires communication time Ω(g ·min(m/p, n)), where g is the gap parameter of the BSP model. In addition, we present two algorithms whose running times match the lower bounds in different situations. Both algorithms perform linear work and use a number of supersteps independent of the input size. The first algorithm is simple but can employ at most m/n processors efficiently. Hence, it should be applied in situations where the input graph is relatively dense. The second algorithm is a randomized algorithm that performs linear work with high probability, provided that m ≥ n · log p. This is the first linear work BSP algorithm for finding an MST in sparse graphs