{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:56:37Z","timestamp":1787385397460,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>A basic problem in graphs and hypergraphs is that of finding a large independent set---one of guaranteed size. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107] have shown a certain lower bound $\\alpha_k(H)$ on the size of a maximum independent set in a given k-uniform hypergraph H and have also presented an efficient sequential algorithm to find an independent set of size $\\alpha_k(H)$. They also show that $\\alpha_k(H)$ is the size of the maximum independent set for various hypergraph families. Here, we show that an RNC algorithm due to Beame and Luby [in Proceedings of the ACM--SIAM Symposium on Discrete Algorithms, 1990, pp. 212--218] finds an independent set of expected size $\\alpha_k(H)$ and also derandomizes it for certain special cases. (An intriguing conjecture of Beame and Luby implies that understanding this algorithm better may yield an RNC algorithm to find a maximal independent set in hypergraphs, which is among the outstanding open questions in parallel computation.) We also present lower bounds on independent set size for nonuniform hypergraphs using this algorithm. For graphs, we get an NC algorithm to find independent sets of size essentially that guaranteed by the general (degree-sequence based) version of Tur\u00e1n's theorem.<\/jats:p>","DOI":"10.1137\/s0895480102419731","type":"journal-article","created":{"date-parts":[[2005,1,10]],"date-time":"2005-01-10T21:00:25Z","timestamp":1105390825000},"page":"488-500","source":"Crossref","is-referenced-by-count":14,"title":["Finding Large Independent Sets in Graphs and Hypergraphs"],"prefix":"10.1137","volume":"18","author":[{"given":"Hadas","family":"Shachnai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"R3","unstructured":", Proceedings of the First Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (SIAM), 1990, 0\u20130, xiv+523, Held in San Francisco, California, January 22\u201324, 199091i:68006"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150110"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90228-N"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0218029"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0406036"},{"key":"R10","volume-title":"Analysis of algorithms","author":"Hofri Micha","year":"1995"},{"key":"R11","unstructured":"PiotrIndyk, A small approximately min\u2010wise independent family of hash functions, ACM, New York, 1999, 454\u20134562000m:68183"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1532"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"RichardKarp, VijayaRamachandran, Parallel algorithms for shared\u2010memory machines, Elsevier, Amsterdam, 1990, 869\u20139411127183","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90027-X"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4226"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"P. Kelsen,\n                      On the parallel complexity of computing a maximal independent set in a hypergraph\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 339\u2013350.","DOI":"10.1145\/129712.129745"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0884"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/18.272452"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010046"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"N. Nisan,\n                      RL\u2286SC\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 619\u2013623.","DOI":"10.1145\/129712.129772"},{"key":"R24","unstructured":"R. Sedgewick and P. Flajolet,\n                      An Introduction to the Analysis of Algorithms\n                      , Addison\u2013Wesley, Reading, MA, 1996."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"D. Sivakumar,\n                      Algorithmic derandomization via complexity theory\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 619\u2013626.","DOI":"10.1145\/509907.509996"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"JoelSpencer, The probabilistic lens: Sperner, Tur\u00e1n and Bregman revisited, Cambridge Univ. Press, Cambridge, 1990, 391\u201339692i:05127","DOI":"10.1017\/CBO9780511983917.033"},{"key":"R27","unstructured":"E. Szyma\u0144ska,\n                      Derandomization of a parallel MIS algorithm in a linear hypergraph\n                      , in Proceedings of the International Colloquium on Automata, Languages and Programming, Satellite Workshops, Carleton Scientific, Waterloo, Canada, 2000, pp. 39\u201352."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-19-30"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480102419731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:01:02Z","timestamp":1787320862000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480102419731"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0895480102419731"],"URL":"https:\/\/doi.org\/10.1137\/s0895480102419731","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}