COMPUTING MANY MAXIMAL INDEPENDENT SETS FOR HYPERGRAPHS IN PARALLEL
Abstract
A hypergraph
is called uniformly δ-sparse if for every nonempty subset X ⊆ V of vertices, the average degree of the sub-hypergraph of
induced by X is at most δ. We show that there is a deterministic algorithm that, given a uniformly δ-sparse hypergraph
, and a positive integer k, outputs k or all minimal transversals for
in O(δlog(1 + k)polylog(δ|V|))-time using |V|O(logδ)kO(δ) processors. Equivalently, the algorithm can be used to compute in parallel k or all maximal independent sets for
.
This research was supported in part by the National Science Foundation, grant, IIS-0118635. The third author is also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.
References
- J. Algorithms 7, 567 (1986), DOI: 10.1016/0196-6774(86)90019-2. Crossref, ISI, Google Scholar
-
M. Anthony and N. Biggs , Computational Learning Theory ( Cambridge University Press , 1992 ) . Google Scholar P. Beame and M. Luby , Parallel search for maximal independence given minimal dependence, Proceedings of the First SODA Conference (1990) pp. 212–218. Google Scholar-
C. Berge , Hypergraphs ,North Holland Mathematical Library 445 ( Elsevier-North Holland , Amestrdam , 1989 ) . Google Scholar - Parallel Processing Letters 10, 253 (2000), DOI: 10.1142/S0129626400000251. Link, ISI, Google Scholar
E. Boros , Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections, Proceedings of the 6th Latin American Theoretical Informatics Conference (LATIN 2004),LNCS 2976, ed.Martin Farach-Colton pp. 488–498. Google Scholar- SIAM Journal on Computing 31(5), 1624 (2002), DOI: 10.1137/S0097539701388768. Crossref, ISI, Google Scholar
- Optimization Methods and Software 10, 147 (1998), DOI: 10.1080/10556789808805708. Crossref, ISI, Google Scholar
A. Broder , M. Charikar and M. Mitzenmacher , A derandomization using min-wise independent permutations, RANDOM'98, eds.M. Luby , J. Rolim and M. Serna (1998) pp. 15–24. Google Scholar-
C. J. Colbourn , The combinatorics of network reliability ( Oxford University Press , 1987 ) . Google Scholar E. Dahlhaus and M. Karpinski , A fast parallel algorithm for computing all maximal cliques in a graph and the related problems, Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT),LNCS 318 pp. 139–144. Google Scholar- Inf. Process. Lett. 42(6), 309 (1992), DOI: 10.1016/0020-0190(92)90228-N. Crossref, ISI, Google Scholar
- Machine Learning 37, 89 (1999), DOI: 10.1023/A:1007627028578. Crossref, ISI, Google Scholar
- SIAM Journal on Computing 24, 1278 (1995), DOI: 10.1137/S0097539793250299. Crossref, ISI, Google Scholar
-
T. Eiter , G. Gottlob and K. Makino , New results on monotone dualization and generating hypergraph transversals , The 34th Annual ACM Symposium on Theory of Computing (STOC) ( 2002 ) , DOI: 10.1145/509907.509912 . Google Scholar - J. Algorithms 21, 618 (1996), DOI: 10.1006/jagm.1996.0062. Crossref, ISI, Google Scholar
- Information Processing Letters 58(2), 55 (1996), DOI: 10.1016/0020-0190(96)00040-3. Crossref, ISI, Google Scholar
- SIAM J. Disc. Math. 2, 322 (1989), DOI: 10.1137/0402028. Crossref, Google Scholar
- SIAM J. Computing 18, 419 (1989), DOI: 10.1137/0218029. Crossref, ISI, Google Scholar
- USSR Comput. Math. and Math. Phys. 13(6), 1485. Google Scholar
- USSR Comput. Math. and Math. Phys. 15(2), 357 (1975). Google Scholar
- J. Algorithms 38(1), 84 (2001), DOI: 10.1006/jagm.2000.1131. Crossref, ISI, Google Scholar
- Information Processing Letters 27, 119 (1988), DOI: 10.1016/0020-0190(88)90065-8. Crossref, ISI, Google Scholar
- JACM 32, 762 (1985), DOI: 10.1145/4221.4226. Crossref, ISI, Google Scholar
- Journal of Computer and System Science 36, 225 (1988), DOI: 10.1016/0022-0000(88)90027-X. Crossref, ISI, Google Scholar
-
P. Kelsen , On the parallel complexity of computing a maximal independent set in a hypergraph , Proceedings of the 24-th Anual ACM STOC Conference ( 1992 ) , DOI: 10.1145/129712.129745 . Google Scholar - Information Processing Letters 101(4), 148 (2007), DOI: 10.1016/j.ipl.2006.09.006. Crossref, ISI, Google Scholar
- SIAM Journal on Computing 9, 558 (1980), DOI: 10.1137/0209042. Crossref, ISI, Google Scholar
- J. Algorithms 25(2), 311 (1997). Crossref, ISI, Google Scholar
-
K. G. Ramamurthy , Coherent Structures and Simple Games ( Kluwer Academic Publishers , 1990 ) . Crossref, Google Scholar - Annals of Discrete Mathematics 2, 107 (1978). Crossref, ISI, Google Scholar
E. Szymanska , Derandomization of a parallel MIS algorithm in a linear hypergraph, Proc. 4th International Workshop on Randomization and Approximation Techniques in Computer Science (2000) pp. 39–52. Google Scholar


