Generating maximal independent sets for hypergraphs with bounded edge-intersections

Given a finite set V, and integers k greater than or equal to 1 and r greater than or equal to 0, denote by A(k, r) the class of hypergraphs A subset of or equal to 2(V) with (k, r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem MIS(A, I): given a hypergraph A and a subfamily I subset of or equal to I(A), of its maximal independent sets (MIS) T(A), either extend this subfamily by constructing a new MIS I is an element of I(A)\I or prove that there are no more MIS, that is I = I(A). We show that for hypergraphs A is an element of A(k, r) with k + r less than or equal to const, problem MIS (A, I) is NC-reducible to problem MIS(A', circle divide) of generating a single MIS for a partial subhypergraph A' of A. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A(1, c), A(c, 0), and A(2, 1), where c is a constant. We also show that, for A is an element of A(k, r), where k + r less than or equal to const, the problem of generating all MIS of A can be solved in incremental polynomial-time with space polynomial only in the size of A.