On the parallel complexity of computing a maximal independent set in a hypergraph

ABSTRACT

A maximal independent set in a hypergraph is a subset of vertices that is maximal with respect to the property of not containing any edge of the hypergraph. We show that an algorithm proposed by Beame and Luby is in randomized NC for hypergraphs in which the maximum edge size is bounded by a constant. To prove this, we bound the upper tail of sums of dependent random variables defined on the edges of a hypergraph. These bounds may be viewed as extensions of bounds on the tail of the binomial distribution. We derandomize this algorithm to obtain the first sublinear time deterministic algorithm for hypergraphs with edges of size O(1). The algorithm exhibits the following time-processor tradeoff: it can be made to run in time O(n&egr;) with nO(1/&egr;) processors for a hypergraph on n vertices, for any &egr; ≥ 2d+1• (log log n)/(log n); here d = O(1) denotes the maximum size of an edge in H. In particular, for any constant &egr; > O, we have an algorithm running in time O(n&egr;) on a polynomial number of processors, and we have an algorithm running in time (log n)O(1) on nO(log n/log log n) processors.

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: P. Beame, Personal Communication, 1991.
• 3: 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
• 4: Bonnie Berger, Simulating (logcn)-wise independence in NC, Journal of the ACM (JACM), v.38 n.4, p.1026-1046, Oct. 1991 [doi>10.1145/115234.115347]
• 5: E. Dahlhaus, M. Karpinski, An efficient algorithm for the 3MIS problem, Technical report TR-89-052, September 1989, International Computer Science institute, Berkeley, CA.
• 6: 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]
• 7: 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]
• 8: Mark Goldberg , Thomas Spencer, Constructing a maximal independent set in parallel, SIAM Journal on Discrete Mathematics, v.2 n.3, p.322-328, August 1989 [doi>10.1137/0402028]
• 9: 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
• 10: 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]
• 11: 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]
• 12: P. Kelsen, An efficient parallel algorithm for finding an mis in hypergraphs of dimension 3, manuscript, Department of Computer Sciences, University of Texas, Austin, TX, January 1990.
• 13: 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]
• 14: M. Luby, Removing randomness in parallel computation without a processor penalty, 29th FOCS, 1988, pp. 162-173.
• 15: Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
• 16: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Performance, Theory