Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching

Understand

The success of modern parallel paradigms such as MapReduce, Hadoop, or Spark, has attracted a significant attention to the Massively Parallel Computation (MPC) model over the past few years, especially on graph problems.

• In this work, we consider symmetry breaking problems of maximal independent set (MIS) and maximal matching (MM), which are among the most intensively studied problems in distributed/parallel computing, in MPC.
• These problems are known to admit efficient MPC algorithms if the space per machine is near-linear in $n$, the number of vertices in the graph.
• This space requirement however, as observed in the literature, is often significantly larger than we can afford; especially when the input graph is sparse.