Finding large independent sets of hypergraphs in parallel

ABSTRACT

A basic problem in hypergraphs is that of finding a large independent set-one of guaranteed size-in a given hypergraph. 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, Vol. 15, pp. 99-107, 1991) have shown a certain lower bound &agr;k(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficien sequential algorithm to find an independent set of size &agr;k (H). They also show that &agr;k (H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size &agr;k(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16:434-449, 1996.
• 3: N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, 1992.
• 4: Paul Beame , Michael Luby, Parallel search for maximal independence given minimal dependence, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.212-218, January 22-24, 1990, San Francisco, California, United States
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 6: Yair Caro , Zsolt Tuza, Improved lower bounds on k-independence, Journal of Graph Theory, v.15 n.1, p.99-107, March 1991 [doi>10.1002/jgt.3190150110]
• 7: Elias Dahlhaus , Marek Karpinski , Pierre Kelsen, An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3, Information Processing Letters, v.42 n.6, p.309-313, July 24, 1992 [doi>10.1016/0020-0190(92)90228-N]
• 8: C. M. Fortuin, J. Ginibre, P. N. Kasteleyn, Correlational Inequalities for Partially Ordered Sets, Communications of Mathematical Physics, 22,pp. 89-103, 1971.
• 9: Mark Goldberg , Thomas Spencer, A new parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.18 n.2, p.419-427, April 1989 [doi>10.1137/0218029]
• 10: Mark Goldberg , Thomas Spencer, An efficient parallel algorithm that finds independent sets of guaranteed size, SIAM Journal on Discrete Mathematics, v.6 n.3, p.443-459, Aug. 1993 [doi>10.1137/0406036]
• 11: M. Hofri. Analysis of Algorithms. Oxford University Press, 1995.
• 12: Piotr Indyk, A small approximately min-wise independent family of hash functions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.454-456, January 17-19, 1999, Baltimore, Maryland, United States
• 13: David R. Karger , Daphne Koller, (De)randomized construction of small samples spaces in NC, Journal of Computer and System Sciences, v.55 n.3, p.402-413, Dec. 1997 [doi>10.1006/jcss.1997.1532]
• 14: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 15: Richard M. Karp , Eli Upfal , Avi Wigderson, The complexity of parallel search, Journal of Computer and System Sciences, v.36 n.2, p.225-253, April 1988 [doi>10.1016/0022-0000(88)90027-X]
• 16: Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Journal of the ACM (JACM), v.32 n.4, p.762-773, Oct. 1985 [doi>10.1145/4221.4226]
• 17: Pierre Kelsen, On the parallel complexity of computing a maximal independent set in a hypergraph, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.339-350, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129745]
• 18: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 19: Tomasz Łuczak , Edyta Szymańska, A parallel randomized algorithm for finding a maximal independent set in a linear hypergraph, Journal of Algorithms, v.25 n.2, p.311-320, Nov. 1997 [doi>10.1006/jagm.1997.0884]
• 20: R. J. McEliece and K. N. Sivarajan. Performance limits for channelized cellular telephone systems. IEEE Trans. Info. Theory, 40(1):21-34, 1994.
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 23: J. H. Spencer. The probabilistic lens: Sperner, Turan and Bregman revisited. In A Tribute to Paul Erdos (A. Baker, B. Bollobas, A. Hajnal, Eds.), Cambridge Univ. Press, pp. 391-396, 1990.
• 24: Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
• 25: E. Szymanska. Derandomization of a Parallel MIS Algorithm in a Linear Hypergraph. In Proc. Fourth International Workshop on Randomization and Approximation Techniques in Computer Science, pages 39-52, 2000.
• 26: P. Turan. On the theory of graphs. Colloq. Math., 3, pp. 19-30, 1954.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Measurement, Performance, Theory, Verification

Keywords:
hypergraphs, independent sets, parallel algorithms, randomized algorithms