zbMATH — the first resource for mathematics

A fast and simple randomized parallel algorithm for the maximal independent set problem. (English) Zbl 0631.68063
Summary: A simple parallel randomized algorithm to find a maximal independent set in a graph \(G = (V, E)\) on \(n\) vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with \(O(|E|d_{\max})\) processors is \(O(\log n)\), where \(d_{\max}\) denotes the maximum degree. On an exclusive-read exclusive-write PRAM with \(O(|E|)\) processors the algorithm runs in \(O(\log^2n)\). Previously, an \(O(\log^4n)\) deterministic algorithm was given by R. M. Karp and A. Wigderson [Proc. 16th Ann. ACM Symp. Theory of Computing, STOC 1984, 266–272 (1984); see also J. Assoc. Comput. Mach. 32, 762–773 (1985; Zbl 0633.68026)] for the EREW-PRAM model. This was recently (independently of our work) improved to \(O(\log^2n)\) by M. Luby [Proc. 17th ACM Symp. Theory of Computing, STOC 1985, 1–10 (1985); see also SIAM J. Comput. 15, 1036–1053 (1986; Zbl 0619.68058)].
In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on \(d\)-wise rather than fully independent random choices (for some constant \(d)\) can be converted into deterministic algorithms. We apply a technique due to A. Joffe [Ann. Probab. 2, 161–162 (1974; Zbl 0276.60005)] and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science
68W20 Randomized algorithms
Full Text: DOI