Faster Deterministic Distributed MIS and Approximate Matching

We present an Õ(log2 n) round deterministic distributed algorithm for the maximal independent set problem. By known reductions, this round complexity extends also to maximal matching, Δ+1 vertex coloring, and 2Δ−1 edge coloring. These four problems are among the most central problems in distributed graph algorithms and have been studied extensively for the past four decades. This improved round complexity comes closer to the Ω(logn) lower bound of maximal independent set and maximal matching [Balliu et al. FOCS ’19]. The previous best known deterministic complexity for all of these problems was Θ(log3 n). Via the shattering technique, the improvement permeates also to the corresponding randomized complexities, e.g., the new randomized complexity of Δ+1 vertex coloring is now Õ(log2logn) rounds.