A Time-Optimal Randomized Parallel Algorithm for MIS

We present a randomized parallel algorithm, in the Exclusive-Read Exclusive-Write (EREW) PRAM model, that computes a Maximal Independent Set (MIS) in O(log n) time and using O(m log2 n) work, with high probability. Thus, MIS ∊ RNC1. This time complexity is optimal and it improves on the celebrated O(log2 n) time algorithms of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86], which had remained the state of the art for the past 35 years.