×

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
PDF BibTeX XML Cite
Full Text: DOI