Parallel Algorithms for Local Problems in Sparse Graphs

Locally checkable problems, such as vertex coloring and maximal independent set (MIS), have recently received a lot of attention in the study of (massively) parallel graph algorithms. In the sublinear regime of the Massively Parallel Computation (MPC) model, a standard technique to approach these problems is to sparsify the input graph and to efficiently simulate a distributed message-passing algorithm in the sparse graph. The focus in the algorithm design is typically on the sparsification step. Often, sophisticated steps are taken to turn the input graph into a sparse representation. Once the graph is sparsified, one applies a naïve algorithm to handle the sparse graph. Especially for MIS, the current techniques for sparsification seem to have hit a wall and we do not know how to push forward.
In this talk, we focus on the second step of the sparsification framework. We discuss algorithms for graphs that are already sparse where the sparsification step becomes irrelevant and nevertheless, many problems remain hard. We pay particular attention to the total space used in the algorithms and give algorithmic techniques tailored for sparse graphs.