A Simple Parallel Algorithm for the Maximal Independent Set Problem

TLDR

Randomization removal is a general, powerful technique for algorithm design. The paper develops two basic design strategies to create a very simple and fast parallel algorithm for the maximal independent set problem. The algorithm assigns identical copies of a simple routine to local input portions, executing them in parallel to quickly produce correct MIS output, and then converts the Monte Carlo version into a deterministic one with the same parallel runtime. The parallel algorithm produces correct MIS output rapidly, and its deterministic conversion retains the same parallel running time.

Abstract

Two basic design strategies are used to develop a very simple and fast parallel algorithms for the maximal independent set (MIS) problem. The first strategy consists of assigning identical copies of a simple algorithm to small local portions of the problem input. The algorithm is designed so that when the copies are executed in parallel the correct problem output is produced very quickly. A very simple Monte Carlo algorithm for the MIS problem is presented which is based upon this strategy. The second strategy is a general and powerful technique for removing randomization from algorithms. This strategy is used to convert the Monte Carlo algorithm for this MIS problem into a simple deterministic algorithm with the same parallel running time.