{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T20:25:46Z","timestamp":1768854346690,"version":"3.49.0"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T00:00:00Z","timestamp":1467072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF Awards","award":["CNS-1010789 and CCF-1422569"],"award-info":[{"award-number":["CNS-1010789 and CCF-1422569"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,6,28]]},"abstract":"\n 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 of processors used is polynomial and the (expected) runtime is polylogarithmic in the size of the input. Unlike the well-understood case of MIS in graphs, for the hypergraph problem, our knowledge is quite limited despite considerable work. It is known that the problem is in RNC when the edges of the hypergraph have constant size. For general hypergraphs with\n n<\/jats:italic>\n vertices and\n m<\/jats:italic>\n edges, the fastest previously known algorithm works in time\n O<\/jats:italic>\n (\u221a\n n<\/jats:italic>\n ) with poly(\n m,n<\/jats:italic>\n ) processors. In this article, we give an EREW PRAM randomized algorithm that works in time\n n<\/jats:italic>\n \n o<\/jats:italic>\n (1)\n <\/jats:sup>\n with\n O<\/jats:italic>\n (\n n<\/jats:italic>\n +\n mlog n<\/jats:italic>\n ) processors on general hypergraphs satisfying\n m<\/jats:italic>\n \u2264\n n<\/jats:italic>\n \n o<\/jats:italic>\n (1) log log\n n<\/jats:italic>\n \/log log log\n n<\/jats:italic>\n <\/jats:sup>\n . We also give an EREW PRAM deterministic algorithm that runs in time\n n<\/jats:italic>\n \u03f5<\/jats:sup>\n on a graph with\n m<\/jats:italic>\n \u2264\n n<\/jats:italic>\n 1\/\u03b4<\/jats:sup>\n edges, for any constants \u03b4, \u03f5; the number of processors is polynomial in\n m, n<\/jats:italic>\n for a fixed choice of \u03b4, \u03f5. Our algorithms are based on a sampling idea that reduces the dimension of the hypergraph and employs the algorithm for constant dimension hypergraphs as a subroutine.\n <\/jats:p>","DOI":"10.1145\/2938436","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T13:26:34Z","timestamp":1470317194000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["On Computing Maximal Independent Sets of Hypergraphs in Parallel"],"prefix":"10.1145","volume":"3","author":[{"given":"Ioana O.","family":"Bercea","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Navin","family":"Goyal","sequence":"additional","affiliation":[{"name":"Microsoft Research India, Bangalore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David G.","family":"Harris","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 212--218","author":"Beame P.","year":"2020","unstructured":"P. Beame and M. Luby . 1990. Parallel search for maximal independence given minimal dependence . In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 212--218 . http:\/\/portal.acm.org\/citation.cfm?id=3 2020 0. P. Beame and M. Luby. 1990. Parallel search for maximal independence given minimal dependence. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 212--218. http:\/\/portal.acm.org\/citation.cfm?id=320200."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90027-X"},{"key":"e_1_2_1_3_1","volume-title":"Karp and Vijaya Ramachandran","author":"Richard","year":"1990","unstructured":"Richard M. Karp and Vijaya Ramachandran . 1990 . Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity (A). 869-- 942 . Richard M. Karp and Vijaya Ramachandran. 1990. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A). 869--942."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129745"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0884"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Warren Schudy and Maxim Sviridenko. 2012. Concentration and moment inequalities for polynomials of independent random variables. In SODA. 437--446. Warren Schudy and Maxim Sviridenko. 2012. Concentration and moment inequalities for polynomials of independent random variables. In SODA. 437--446.","DOI":"10.1137\/1.9781611973099.37"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102419731"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938436","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2938436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:38:20Z","timestamp":1750282700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938436"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":8,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,28]]}},"alternative-id":["10.1145\/2938436"],"URL":"https:\/\/doi.org\/10.1145\/2938436","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,28]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}