article

Free access

A fast parallel algorithm for the maximal independent set problem

Authors:

Richard M. Karp,

Avi WigdersonAuthors Info & Claims

Journal of the ACM (JACM), Volume 32, Issue 4

Pages 762 - 773

https://doi.org/10.1145/4221.4226

Published: 01 October 1985 Publication History

PDF eReader

Abstract

A parallel algorithm is presented that accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n)⁴) time and uses O((n/(log n))³) processors, where n is the number of vertices in G. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.

References

[1]

COOK, S. A.An overview of computational complexity. Commun. ACM 26, 6 (1983), 400-408.

Crossref

Google Scholar

[2]

COOK, S. A.The classification of problems which have fast parallel algorithms. Tech. Rep. No. 164/83, Dept. of Comput. Sci., Univ. of Toronto, Toronto, Ont., Canada, 1983.

Google Scholar

[3]

HALL, M.Combinatorial Theory. Blaisdell, Waltham, Mass., 1967.

Google Scholar

[4]

JONES, N. D., LIEN, Y. E., AND LAASER, W. T.New problems complete for nondeterministic log space. Math. Syst. Theory 10 (1976), 1-17.

Google Scholar

[5]

LEV, G. Size bounds and parallel algorithms for networks. Rep. CST-8-80, Dept. of Comput. Sci., Univ. of Edinburgh, Edinburgh, Scotland, 1980.

Google Scholar

[6]

VALIANT, L. G. Parallel computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. IBM, New York, 1982.

Google Scholar

Cited By

View all

Harvey NSahami AMohar BShinkar IO'Donnell R(2024)Explicit Orthogonal Arrays and Universal Hashing with Arbitrary ParametersProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649642(1259-1267)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649642
Blin LDurand ATixeuil S(2024)Resource efficient stabilization for local tasks despite unknown capacity linksTheoretical Computer Science10.1016/j.tcs.2024.1147441013(114744)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114744
Thành L(2023)The Hsu–Robbins–Erdös theorem for the maximum partial sums of quadruplewise independent random variablesJournal of Mathematical Analysis and Applications10.1016/j.jmaa.2022.126896521:1(126896)Online publication date: May-2023
https://doi.org/10.1016/j.jmaa.2022.126896
Show More Cited By

Index Terms

A fast parallel algorithm for the maximal independent set problem

Recommendations

An improved distributed algorithm for maximal independent set
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which ...
A fast parallel algorithm for the maximal independent set problem
STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing

A parallel algorithm is presented which accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n)⁴) time and uses O((n/log ...
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Special Issue for SPAA 2014

Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Essentially, the challenge is to design (randomized) algorithms in which the number ...

Reviews

Reviewer: Christoph M. Hoffmann

An independent set of a simple graph is a subset of vertices, no two of which are adjacent. The paper describes a P-RAM algorithm to determine a maximal independent set for a given graph. The bounds achieved are O((log n) 4) deterministic time with O( n 3/(log n) 3) processors. There is also a sketch of a probabilistic algorithm requiring O( n 2) processors taking O((log n) 3) expected time. The basic strategy is to select an independent set and repeatedly add to it. The difficulty consists of selecting sufficiently large subsets at each adding stage. By means of combinatorial arguments, it is shown that these sets should be located within subsets of vertices of above average valence. The subsets can be chosen at random, leading to a probabilistic algorithm, or deterministically, the latter requiring a balanced incomplete block design.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 32, Issue 4

Oct. 1985

234 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/4221

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1985

Published in JACM Volume 32, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

198
Total Citations
View Citations
1,431
Total Downloads

Downloads (Last 12 months)188
Downloads (Last 6 weeks)26

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Harvey NSahami AMohar BShinkar IO'Donnell R(2024)Explicit Orthogonal Arrays and Universal Hashing with Arbitrary ParametersProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649642(1259-1267)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649642
Blin LDurand ATixeuil S(2024)Resource efficient stabilization for local tasks despite unknown capacity linksTheoretical Computer Science10.1016/j.tcs.2024.1147441013(114744)Online publication date: Oct-2024
https://doi.org/10.1016/j.tcs.2024.114744
Thành L(2023)The Hsu–Robbins–Erdös theorem for the maximum partial sums of quadruplewise independent random variablesJournal of Mathematical Analysis and Applications10.1016/j.jmaa.2022.126896521:1(126896)Online publication date: May-2023
https://doi.org/10.1016/j.jmaa.2022.126896
Balliu ABrandt SKuhn FOlivetti DLeonardi SGupta A(2022)Distributed ∆-coloring plays hide-and-seekProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520027(464-477)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520027
Balliu ABrandt SOlivetti D(2022)Distributed Lower Bounds for Ruling SetsSIAM Journal on Computing10.1137/20M138177051:1(70-115)Online publication date: 8-Feb-2022
https://doi.org/10.1137/20M1381770
Goles ELeal LMontealegre PRapaport IRíos-Wilson M(2022)Distributed maximal independent set computation driven by finite-state dynamicsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2022.215324838:1(85-97)Online publication date: 6-Dec-2022
https://doi.org/10.1080/17445760.2022.2153248
Vanetik N(2022)Graph support measures and flowsSocial Network Analysis and Mining10.1007/s13278-022-00955-z12:1Online publication date: 25-Aug-2022
https://doi.org/10.1007/s13278-022-00955-z
Giannoula CPeppas AGoumas GKoziris N(2022)High-performance and balanced parallel graph coloring on multicore platformsThe Journal of Supercomputing10.1007/s11227-022-04894-679:6(6373-6421)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04894-6
Balliu ABrandt SKuhn FOlivetti DMiller ACensor-Hillel K(2021)Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in TreesProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467901(283-293)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467901
Czumaj ADavies PParter M(2021)Graph Sparsification for Derandomizing Massively Parallel Computation with Low SpaceACM Transactions on Algorithms10.1145/345199217:2(1-27)Online publication date: 6-Jun-2021
https://dl.acm.org/doi/10.1145/3451992
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

An improved distributed algorithm for maximal independent set