Pierre Kelsen
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ε) with nO(1/ε) processors for a hypergraph on n vertices, for any ε ≥ 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 ε > O, we have an algorithm running in time O(nε) 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.
- 1.N. Alon, L. Babai, A. itai, A fast randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7, pp. 567-583, 1986. Google Scholar
Digital Library
- 2.P. Beame, Personal Communication, 1991.Google Scholar
- 3.P. Beame, M. Luby, Parallel Search for Maximal independence Given Minimal Dependence, Proceedings of the First SODA Conference, 1990, pp. 212- 218. Google ScholarDigital Library
- 4.B. Berger, J. Rompel, Simulating (log# n)-wise Independence in NC, JACM, vol. 38, 1991, pp. 1026- 1046. Google ScholarDigital Library
- 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.Google Scholar
- 6.E. Dahlhaus, M. Karpinski, P. Kelsen, An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3, information Processing Letters, to appear. Google ScholarDigital Library
- 7.M. Goldberg, T. Spencer, A new parallel algorithm for the maximal independent set problem, SIAM J. Computing, vol. 18, 1989, pp.419-427. Google ScholarDigital Library
- 8.M. Goldberg, T. Spencer, Constructing a Maximal Independent Set in Parallel, SIAM J. Disc. Math., vol. 2, 1989, pp. 322-328. Google ScholarDigital Library
- 9.R. Karp, V. Ramachandran, Parallel algorithms for shared memory machines, in Handbook of Theoretical Computer Science, J. Van Leeuwen, ed., North Holland, 1990, pp.869-941. Google ScholarDigital Library
- 10.R. Karp, A. Wigderson, A fast parallel algorithm for the maximal independent set problem, JACM 32 (1985), pp. 762-773. Google ScholarDigital Library
- 11.R. Karp, E. Upfal, A. Wigderson, The complexity of parallel search, JCSS, vol. 36, 1988, pp.225-253. Google ScholarDigital Library
- 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.Google Scholar
- 13.M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Computing, vol. 15, 1986, pp. 1036-1053. Google ScholarDigital Library
- 14.M. Luby, Removing randomness in parallel computation without a processor penalty, 29th FOCS, 1988, pp. 162-173.Google ScholarDigital Library
- 15.R. Motwani, J. Naor, M. Naor, The probabilistic method yields deterministic parallel algorithms, 30th FOCS, 1989, pp. 8-13. Google ScholarDigital Library
- 16.P. Raghavan, Probabilistic construction of deterministic algorithms: Approximating packing integer programs, JCSS, vol. 37, 1988, pp. 130-143. Google ScholarDigital Library
Index Terms
- On the parallel complexity of computing a maximal independent set in a hypergraph
Recommendations
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Special Issue for SPAA 2014Whether 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 ...
On computing maximal independent sets of hypergraphs in parallel
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architecturesWhether 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. Unlike the well-understood case of MIS in graphs, for the hypergraph problem, our ...
Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
A parallel algorithm for maximal independent set (MIS) in hypergraphs has been a long-standing algorithmic challenge, dating back nearly 30 years to a survey of Karp and Ramachandran (1990). The best randomized parallel algorithm for hypergraphs of ...
Comments