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.

MSC:
 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: