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.

I would suggest reading Theorem 5.1 and Lemma 5.1 on the same page in the paper. They answer both your questions.

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.

| cite | improve this answer | |
  • $\begingroup$ Welcome to CS Stack Exchange! $\endgroup$ – David Richerby Jul 25 '15 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.