## Communication-Optimal Parallel Minimum Spanning Tree Algorithms

Micah Adler, Wolfgang Dittrich, Ben Juurlink, Miroslaw Kutylowski and Ingo Rieping

#### Abstract

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 $\Omega(\kappa \cdot \min(m, pn))$ bits need to be transmitted in order to solve the MST problem, where $\kappa$ is the number of bits required to represent a single edge weight. This implies that if each message contains $\kappa$ bits, any BSP algorithm for finding an MST requires communication time $\Omega(g \cdot \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 \geq n \cdot \log p$. This is the first linear work BSP algorithm for finding an MST in sparse graphs.

Full paper in compressed Postscript format.