Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph

✍ Scribed by H. Chen; A. M. Frieze

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 726 KB
• Volume: 9
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199612)9:4<359::aid-rsa2>3.0.co;2-w

✦ Synopsis

It is well known [9] that finding a maximal independent set in a graph is in class J%, and [lo] that finding a maximal independent set in a hypergraph with fixed dimension is in %JV"%' . It is not known whether this latter problem remains in A% when the dimension is part of the input. We will study the problem when the problem instances are randomly chosen. It was shown in [6] that the expected running time of a simple parallel algorithm for finding the lexicographically first maximal independent set (Ifrnis) in a random simple graph is logarithmic in the input size. In this paper, we will prove a generalization of this result. We show that if a random k-uniform hypergraph has vertex set {1,2, . . . , n} and its edges are chosen independently with probability p from the set of (;) possible edges, then our algorithm finds the lfrnis in O( ,d$;n ) expected time. The hidden constant is independent of k , p .