# Karloff's algorithm applied to sparse graphs

I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph.

Karloff [1, p.6] has given a map-reduce algorithm called "Finding an MST of a Dense Graph Using Map-Reduce" which finds an MST of $G$ by randomly partitioning the vertices into $k$ different equally sized sets $V_i$ and then finding a MST for $V_i \cup V_j$ for all $i,j$.

will it provide correct output if we will apply this algorithm to a sparse graph, i.e., a graph for which $|E| < N$, instead of a $c$-dense graph? Will it work correctly? If it will, why is the paper making the assumption here $|E| = m \ge N^{1+c}$, if their algorithm works for sparse graphs too?

1. A Model of Computation for MapReduce. Howard Karloff, Siddharth Suri, Sergei Vassilvitskii. ACM-SIAM Symposium on Discrete Algorithms, 2010.

The proof of Theorem 5.1 in the paper does not use the density of $G$. It will therefore also work for sparse graphs.
You are asking about the motivation behind the assumption of $G$ being dense. In this context the assumption is that a dense graph does not fit into the memory of a single machine. Lemma 5.1 and the conclusions after it show that the input size to the reducers is small enough to fit into the memory.